1931. 用三种不同颜色为网格涂色
题目链接
1931. 用三种不同颜色为网格涂色 - 力扣（LeetCode）
题目描述
给你两个整数m和n。构造一个m x n的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。
涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对109 + 7取余 的结果。
题目示例
示例 1 :
输入：m = 1, n = 1 输出：3 解释：如上图所示，存在三种可能的涂色方案。示例 2 :
输入：m = 1, n = 2 输出：6 解释：如上图所示，存在六种可能的涂色方案。解题思路
- 问题理解：
- 给定一个
m x n的网格，用3种颜色涂色，要求相邻网格颜色不同。 - 计算所有合法的涂色方案数，结果对
10^9+7取模。
- 给定一个
- 关键思路：
- 状态压缩：将每列的颜色状态用三进制数表示（0/1/2对应三种颜色）。
- 有效状态筛选：生成所有列内相邻颜色不同的有效状态。
- 状态转移图：构建状态之间的转移关系（相邻列对应位置颜色不同）。
- 记忆化搜索：动态规划计算方案数，避免重复计算。
- 算法流程：
- 预处理3的幂次数组
pow3，用于状态处理。 - 生成所有有效的列颜色状态
valid。 - 构建状态转移图
nxt，表示每个状态可以转移到哪些其他状态。 - 使用记忆化搜索
dfs计算方案数，从最后一列开始递归。 - 汇总所有可能的初始状态的方案数，返回结果。
- 预处理3的幂次数组
题解代码
classSolution{privatestaticfinalintMOD=1_000_000_007;// 模数，防止结果溢出publicintcolorTheGrid(intm,intn){// 计算3的幂次数组，用于后续处理颜色状态int[]pow3=newint[m];pow3[0]=1;for(inti=1;i<m;i++){pow3[i]=pow3[i-1]*3;}// 生成所有有效的列颜色状态（相邻颜色不同）List<Integer>valid=newArrayList<>();next:for(intcolor=0;color<pow3[m-1]*3;color++){for(inti=1;i<m;i++){// 检查相邻颜色是否相同if(color/pow3[i]%3==color/pow3[i-1]%3){continuenext;// 相同则跳过}}valid.add(color);// 有效状态加入列表}// 构建状态转移图：每个有效状态可以转移到哪些其他有效状态intnv=valid.size();List<Integer>[]nxt=newArrayList[nv];Arrays.setAll(nxt,i->newArrayList<>());for(inti=0;i<nv;i++){next2:for(intj=0;j<nv;j++){for(intp3:pow3){// 检查对应位置颜色是否相同if(valid.get(i)/p3%3==valid.get(j)/p3%3){continuenext2;// 相同则跳过}}nxt[i].add(j);// 可以转移的状态}}// 记忆化数组，memo[i][j]表示第i列使用状态j时的方案数int[][]memo=newint[n][nv];for(int[]row:memo){Arrays.fill(row,-1);}// 计算所有可能的初始状态的总方案数longans=0;for(intj=0;j<nv;j++){ans+=dfs(n-1,j,nxt,memo);}return(int)(ans%MOD);}// 记忆化搜索privateintdfs(inti,intj,List<Integer>[]nxt,int[][]memo){if(i==0){return1;// 基础情况：第一列}if(memo[i][j]!=-1){returnmemo[i][j];// 已计算过}longres=0;// 遍历所有可能的下一个状态for(intk:nxt[j]){res+=dfs(i-1,k,nxt,memo);}returnmemo[i][j]=(int)(res%MOD);// 存储并返回结果}}复杂度分析
- 时间复杂度：
- 生成有效状态：O(m * 3^m)
- 构建状态转移图：O(m * 3^(2m))
- 记忆化搜索：O(n * 3^m)
- 总体：O(n * 3^m + m * 3^(2m))，当m较小时可行
- 空间复杂度：
- 存储状态转移图：O(3^(2m))
- 记忆化数组：O(n * 3^m)
- 总体：O(n * 3^m + 3^(2m))