LC1931. 用三种不同颜色为网格涂色【经典状态压缩 DP】
1931. 用三种不同颜色为网格涂色
这道题是典型的状态压缩动态规划（状压 DP）。乍一看可能有些复杂，但只要我们抓住题目中m ≤ 5 m \le 5m≤5这个极其特殊的条件，一步步拆解，思路就会非常清晰。
这种“一宽一窄”的网格问题（n nn大m mm小），标准的套路是按列推进，把每一列的颜色组合看作一个整体（状态）。
#include<vector>classSolution{public:intcolorTheGrid(intm,intn){intMOD=1e9+7;std::vector<int>valid_states;// 辅助函数：检查单列的状态（三进制数）是否合法（上下相邻颜色不同）autoisValidCol=[&](intmask){intprev=-1;for(inti=0;i<m;++i){intcurr=mask%3;// 提取当前格子的颜色 (0, 1, 2)if(curr==prev)returnfalse;prev=curr;mask/=3;}returntrue;};// 1. 找出单列的所有合法状态for(inti=0;i<pow(3,m);++i){if(isValidCol(i)){valid_states.push_back(i);}}// 辅助函数：检查两个合法状态能否相邻（左右相邻颜色不同）autoisValidAdj=[&](intmask1,intmask2){for(inti=0;i<m;++i){if(mask1%3==mask2%3)returnfalse;mask1/=3;mask2/=3;}returntrue;};intnum_states=valid_states.size();std::vector<std::vector<int>>adj(num_states);// 2. 预处理状态转移图// adj[i] 中存储的是可以排在状态 i 后面的所有合法状态的索引for(inti=0;i<num_states;++i){for(intj=0;j<num_states;++j){if(isValidAdj(valid_states[i],valid_states[j])){adj[i].push_back(j);}}}// 3. 动态规划// dp 数组记录到达当前列时，各个状态的方案数std::vector<longlong>dp(num_states,1);// 从第 2 列循环到第 n 列for(intcol=1;col<n;++col){std::vector<longlong>next_dp(num_states,0);for(inti=0;i<num_states;++i){for(intj:adj[i]){// 状态 i 可以转移到状态 jnext_dp[j]=(next_dp[j]+dp[i])%MOD;}}dp=next_dp;}// 4. 汇总最后一列所有状态的方案数longlongans=0;for(longlongcount:dp){ans=(ans+count)%MOD;}returnans;}};算法思路
1. 状态表示与压缩（把一列变成一个数字）
因为有三种颜色（红、绿、蓝），我们自然可以把它们映射为数字0、1、2。
一列有m mm个格子，我们完全可以把这一列的颜色组合看作一个m mm位的三进制数。
- 举个例子：假设m = 3 m = 3m=3。如果一列从上到下涂成了“绿-蓝-红”，对应数字就是
1-2-0。 - 把它当成三进制数120 ( 3 ) 120_{(3)}120(3)，转换为十进制就是1 × 3 2 + 2 × 3 1 + 0 × 3 0 = 15 1 \times 3^2 + 2 \times 3^1 + 0 \times 3^0 = 151×32+2×31+0×30=15。
- 为什么这么做？因为这样我们就可以用一个简单的整数（对于m = 5 m=5m=5，最大也就是3 5 − 1 = 242 3^5 - 1 = 24235−1=242）来唯一代表一整列的涂色方案。这就是所谓的“状态压缩”。
2. 列内合法性筛选（排除上下同色）
并非所有的三进制数都是合法的。题目要求相邻的格子颜色不能相同，这意味着一列之内，上下相邻的格子颜色必须不同。
- 我们遍历从0 00到3 m − 1 3^m - 13m−1的所有数字（即所有可能的涂色组合）。
- 通过不断地对 3 取模（
% 3）和整除（/ 3），我们可以把这个三进制数的每一位（也就是每一个格子的颜色）剥离出来。 - 如果发现相邻两位数字一样（说明上下同色），这个状态就是废弃的；如果都不一样，就把它存入有效状态集合
valid_states中。 - 关键数据：即使在最大的m = 5 m=5m=5时，单列合法的组合最多也只有3 × 2 4 = 48 3 \times 2^4 = 483×24=48种。这个极小的数字是这道题能用 DP 快速求解的基础。
3. 列间合法性预处理（建立状态转移图）
现在我们有了所有合法的单列组合。接下来要解决跨列的问题：把两列拼在一起时，左右相邻的格子颜色也不能相同。
- 如果我们每次 DP 递推时都去重新判断两列能不能相邻，会做很多重复计算。
- 所以，我们在 DP 开始前，提前做一个“配对测试”。我们把所有合法的状态两两组合（比如状态A AA和状态B BB），逐位比较它们的颜色。
- 如果它们在任何一行都没有相同的颜色，说明状态B BB可以合法地紧挨在状态A AA的右边。
- 我们用一个邻接表（数组的数组）
adj把这个关系存下来：adj[A]里面装满了所有可以跟在A AA后面的合法状态。这实际上就是建了一张有向图。
4. 动态规划递推（核心推导）
准备工作做完，终于可以开始涂色了。我们从左到右，一列一列地涂。
状态定义：我们可以定义一个二维数组d p [ i ] [ j ] dp[i][j]dp[i][j]，表示我们涂完了前i ii列，并且第i ii列的涂色状态正好是j jj时，总共有多少种合法的涂色方案。
初始状态（第 1 列）：对于第 1 列，没有任何左侧列的限制。所以每一种合法的单列状态，都能提供 1 种初始方案。
状态转移方程：当我们涂第i ii列并希望它的状态是j jj时，它的方案数取决于第i − 1 i-1i−1列。第i − 1 i-1i−1列必须是那些能和j jj完美相邻的状态（假设为k kk）。
那么，把所有合法的前置状态k kk的方案数加起来，就是当前状态j jj的方案数：
d p [ i ] [ j ] = ∑ d p [ i − 1 ] [ k ] dp[i][j] = \sum dp[i-1][k]dp[i][j]=∑dp[i−1][k]
（其中k kk可以合法地转移到j jj）
空间优化（滚动数组）：你可能会注意到，我们在算第i ii列的时候，只需要用到第i − 1 i-1i−1列的数据，更前面的数据完全没用了。因此，我们在代码里不需要真正开一个n × 48 n \times 48n×48的二维数组，只需要两个一维数组（上一列的
dp和当前列的next_dp）交替更新就可以了。这把空间复杂度从O ( n × 48 ) \mathcal{O}(n \times 48)O(n×48)降到了极小的O ( 48 ) \mathcal{O}(48)O(48)。
最后，当循环跑到第n nn列时，我们把第n nn列所有合法状态对应的方案数全部加起来（并对10 9 + 7 10^9 + 7109+7取模），就是整个网格的涂色方法总数了。
时空复杂度分析
由于这道题有两个独立维度的输入变量：行数m mm和列数n nn，我们的分析需要同时包含这两个变量。
为了让推导更清晰，我们先定义一个核心中间变量：单列的合法状态总数，记为∣ S ∣ |S|∣S∣。
- 在一列中（共m mm个格子），第一个格子有 3 种颜色可选。
- 剩下的m − 1 m-1m−1个格子，为了保证上下颜色不同，每个格子只能从剩下 2 种颜色里选。
- 因此，单列的合法状态数∣ S ∣ = 3 × 2 m − 1 |S| = 3 \times 2^{m-1}∣S∣=3×2m−1。
- 当m mm取最大值 5 时，∣ S ∣ = 3 × 2 4 = 48 |S| = 3 \times 2^4 = 48∣S∣=3×24=48。
时间复杂度分析
算法的执行可以分为三个明确的阶段，我们逐一计算：
寻找单列合法状态：
我们需要遍历所有可能的三进制状态（共3 m 3^m3m种），并对每一个状态花费O ( m ) \mathcal{O}(m)O(m)的时间检查其上下相邻颜色是否合法。
- 耗时：O ( m ⋅ 3 m ) \mathcal{O}(m \cdot 3^m)O(m⋅3m)
预处理状态转移图（建图）：
我们需要两两比对所有合法的状态，判断它们能否左右相邻。合法的状态有∣ S ∣ |S|∣S∣个，因此要进行∣ S ∣ 2 |S|^2∣S∣2次比对。每次比对需要遍历m mm个格子。
- 耗时：O ( m ⋅ ∣ S ∣ 2 ) \mathcal{O}(m \cdot |S|^2)O(m⋅∣S∣2)
动态规划（DP）递推：
这是算法的主循环。我们需要从第 2 列遍历到第n nn列，共进行n − 1 n-1n−1次迭代。
在每一次迭代中，我们要遍历所有∣ S ∣ |S|∣S∣个状态，并查找它能转移到的后续状态。一个合法状态的后续合法状态数量，理论上最多不超过2 m 2^m2m种（因为每一行的右侧格子只有 2 种可用颜色）。所以每次列推导的计算次数受限于∣ S ∣ ⋅ 2 m |S| \cdot 2^m∣S∣⋅2m（或者粗略写成不超过∣ S ∣ 2 |S|^2∣S∣2）。
- 耗时：O ( n ⋅ ∣ S ∣ ⋅ 2 m ) \mathcal{O}(n \cdot |S| \cdot 2^m)O(n⋅∣S∣⋅2m)
综合时间复杂度：
将上述三部分相加为O ( m ⋅ 3 m + m ⋅ ∣ S ∣ 2 + n ⋅ ∣ S ∣ ⋅ 2 m ) \mathcal{O}(m \cdot 3^m + m \cdot |S|^2 + n \cdot |S| \cdot 2^m)O(m⋅3m+m⋅∣S∣2+n⋅∣S∣⋅2m)。
代入∣ S ∣ = 3 × 2 m − 1 |S| = 3 \times 2^{m-1}∣S∣=3×2m−1，并忽略常数项后，最大的主导项显然是 DP 递推部分。
因此，最终的时间复杂度为：
O ( n ⋅ 4 m ) \mathcal{O}(n \cdot 4^m)O(n⋅4m)
现实执行情况：当m = 5 m=5m=5，n = 1000 n=1000n=1000时，n ⋅ 4 5 ≈ 1000 × 1024 ≈ 10 6 n \cdot 4^5 \approx 1000 \times 1024 \approx 10^6n⋅45≈1000×1024≈106次基本操作。这在现代计算机中连几毫秒都用不到，效率极高。
空间复杂度分析
空间开销主要取决于我们在内存中存储了哪些结构：
合法状态数组 (
valid_states)：存储所有合法的单列状态。
- 空间：O ( ∣ S ∣ ) \mathcal{O}(|S|)O(∣S∣)
状态转移邻接表 (
adj)：对于∣ S ∣ |S|∣S∣个状态中的每一个，存储它可以转移到的目标状态。如上文分析，总的边数（转移关系数）最多为∣ S ∣ ⋅ 2 m |S| \cdot 2^m∣S∣⋅2m。
- 空间：O ( ∣ S ∣ ⋅ 2 m ) \mathcal{O}(|S| \cdot 2^m)O(∣S∣⋅2m)
动态规划数组 (
dp和next_dp)：因为我们使用了滚动数组优化，不再需要开辟n × ∣ S ∣ n \times |S|n×∣S∣的二维矩阵，只需要两个长度为∣ S ∣ |S|∣S∣的一维数组交替使用。
- 空间：O ( ∣ S ∣ ) \mathcal{O}(|S|)O(∣S∣)
综合空间复杂度：
主导项是用于存储状态转移关系的邻接表，因此最终的空间复杂度为：
O ( ∣ S ∣ ⋅ 2 m ) ≈ O ( 4 m ) \mathcal{O}(|S| \cdot 2^m) \approx \mathcal{O}(4^m)O(∣S∣⋅2m)≈O(4m)
现实执行情况：当m = 5 m=5m=5时，空间消耗大致是4 5 = 1024 4^5 = 102445=1024个整数类型的内存，这不到几十 KB，空间复杂度可以说是无限接近于O ( 1 ) \mathcal{O}(1)O(1)的极小常数。
需要了解在n nn极大（比如n = 10 9 n = 10^9n=109）的情况下，如何用矩阵快速幂将时间复杂度从O ( n ⋅ 4 m ) \mathcal{O}(n \cdot 4^m)O(n⋅4m)进一步压缩到O ( log n ⋅ 8 m ) \mathcal{O}(\log n \cdot 8^m)O(logn⋅8m)吗？