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

  |  

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

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


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

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


$1 题目

题目链接

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

题目描述

你有一个 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] = dp[u][i - 1] 其中 D[u][v] == 1

代码

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