LeetCode 1411. 给 N x 3 网格图涂色的方案数

Categories:

题目描述
思路分析
1. 解法一：状态 DP（推荐）
相似题目

题目描述

✅ 1411. 给 N x 3 网格图涂色的方案数

思路分析

解法一：状态 DP（推荐）

核心思路：

每行涂色只有两类：三色全不同（ABC）与两色相同（ABA）。

设 a 为 ABC 类数量，b 为 ABA 类数量。

转移：a' = 2a + 2b，b' = 2a + 3b。

复杂度分析：

时间复杂度：O(n)，其中 n 表示行数。

空间复杂度：O(1)。

class Solution {
    public int numOfWays(int n) {
        long mod = 1_000_000_007L;
        long a = 6;
        long b = 6;

        for (int i = 2; i <= n; i++) {
            long na = (2 * a + 2 * b) % mod;
            long nb = (2 * a + 3 * b) % mod;
            a = na;
            b = nb;
        }

        return (int) ((a + b) % mod);
    }
}

func numOfWays(n int) int {
	const mod int64 = 1_000_000_007
	a, b := int64(6), int64(6)

	for i := 2; i <= n; i++ {
		na := (2*a + 2*b) % mod
		nb := (2*a + 3*b) % mod
		a, b = na, nb
	}

	return int((a + b) % mod)
}

相似题目

题目	难度	考察点
1411. 给 N x 3 网格图涂色的方案数	困难	DP
276. 栅栏涂色	中等	DP
256. 粉刷房子	中等	DP
265. 粉刷房子 II	困难	DP
1220. 统计元音字母序列的数目	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/53728246