算法leetcode

【DP难题】力扣1411-给Nx3网格图涂色的方案数

字数统计: 1k字   |   阅读时长: 4分
, ,

摘要: 使用动态规划解决计数问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，最大子数组和这个系列此前连续写了八篇，有些审美疲劳了。今天我们换换脑子，看个使用动态规划解决计数问题的一个例子。

正好在文章 计数DP 中，我们总结了计数问题的常见的场景，以及使用动态规划解决技术问题的方法论，本文我们就来看一个具体的问题。

$1 题目

你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

1
2
3
4
提示：
n == grid.length
grid[i].length == 3
1 <= n <= 5000

示例 1：
输入：n = 1
输出：12
解释：总共有 12 种可行的方法：

示例 2：
输入：n = 2
输出：54

示例 3：
输入：n = 3
输出：246

示例 4：
输入：n = 7
输出：106494

示例 5：
输入：n = 5000
输出：30228214

$2 题解

算法: 计数DP

网格宽度为 3，长度为 N，也就是 N 行 3 列。对于固定的一行，由于只有 3 个格子，每个格子有三种颜色可选，因此一行的颜色组合可能有 3 ^ 3 = 27 种。

我们用一个整数最低的 9 个位来编码一行的颜色组合，具体如下：

前 3 位代表第一列的颜色，中间 3 位代表第二列的颜色，后 3 位代表第三列的颜色。001, 010, 100 分别表示三种颜色。

将所有 27 种颜色组合的编码结果放到一个数组 node 中，其中 node[i] 表示第 i 种颜色组合。

这 27 种颜色组合有的可以相邻，有的不能相邻，颜色组合 node[i] 和颜色组合 node[j] 可以相邻的条件是 node[i] & node[j] == 0。我们可以预处理出可以相邻的颜色组合，记为 D。如果 node[i] 和 node[j] 可以相邻，则记 D[i][j] = 1，否则 D[i][j] = 0

有了一行的颜色编码和可以相邻的颜色编码组合后，我们可以写动态规划的算法了。

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[v][i] := 考虑 [0..i] 行且当前的第 i 行在状态 v 的方案数

答案：
sum(dp[v][n - 1])

初始化：
dp[v][0] = 1

状态转移：
dp[v][i] = sum(dp[u][i - 1])  其中 D[u][v] == 1

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    int numOfWays(int n) {
        for(int i = 1; i <= 3; ++i)
        {
            int state = (1 << (i - 1));
            dfs(state, i, 1);
        }
        int N = node.size();
        D = vector<vector<int>>(N, vector<int>(N));
        for(int i = 0; i < N - 1; ++i)
            for(int j = i + 1; j < N; ++j)
                if(check(i, j))
                    D[i][j] = D[j][i] = 1;

        vector<vector<int>> dp(N, vector<int>(n));
        for(int u = 0; u < N; ++u)
            dp[u][0] = 1;
        for(int i = 1; i < n; ++i)
            for(int u = 0; u < N; ++u)
                for(int v = 0; v < N; ++v)
                    if(D[u][v] == 1)
                        dp[u][i] = (dp[u][i] + (ll)dp[v][i - 1]) % MOD;

        int ans = 0;
        for(int u = 0; u < N; ++u)
            ans = (ans + (ll)dp[u][n - 1]) % MOD;
        return ans;
    }

private:
    vector<int> node; // node[i] := 节点 i 代表的一行颜色状态为 node[i]
    vector<vector<int>> D;
    using ll = long long;
    const int MOD = 1e9 + 7;

    bool check(int i, int j)
    {
        return (node[i] & node[j]) == 0;
    }

    void dfs(int state, int prev, int len)
    {
        if(len == 3)
        {
            node.push_back(state);
            return;
        }
        for(int j = 1; j <= 3; ++j)
        {
            if(j == prev) continue;
            int nxt = state;
            nxt <<= 3;
            nxt |= (1 << (j - 1));
            dfs(nxt, j, len + 1);
        }
    }
};
Share