郴州市网站建设_网站建设公司_加载速度优化_seo优化

题目链接：1411. 给 N x 3 网格图涂色的方案数（困难）

算法原理：

解法：DFS+记忆化搜索

46ms击败15.57%

时间复杂度：O(nmk2m+1)，其中 m=3 是列数，k=3 是颜色数

①整体思路：三种颜色分别用0，1，2表示，利用递归，暴力枚举每一个格子所填的颜色，从下往上填，每行从左往右填，下面Java代码的注释已详细说明

②递归核心：先从最后一行从左往右依次填充颜色，当j==3时说明当前行颜色填充完毕，转到上边一行继续填充，当全部填充完毕，也就是没有上边一行（i==0时），说明找到了一种方案数，返回1

③填充合法性：当前i行j列(i,j)的颜色不能和下边(i-1,j)和左边(i,j-1)颜色相同

④小优化：用key专门标记已深搜过的对应行数的颜色需要的方案数

将当前行坐标(i,j)+刚刚填完的前一行颜色+当前行填完的颜色放进备忘录里，从而减少递归次数

由于0，1，2每个格子颜色仅需要2个比特位，那么存储每行的信息仅需2×3=6个比特位，由于i作为行数，具体需要多少比特位不确定，因此放在一个可以自由活动的区域，也就是最前面，统一<<14个比特位即可

这14个比特位的组成：i的行数(未知比特位位数)+i的列数(j的取值0、1、2仅需2个比特位)+前一行填完的颜色(6个比特位)+当前行颜色（6个比特位）

Java代码：

class Solution { private static final int MOD=1_000_000_007; //全局memo:记忆的内容可以在不同测试数据间共享 private static Map<Integer,Integer> memo=new HashMap<>(); public int numOfWays(int n) { return dfs(n,0,0,0); } //(i,j):i行j列 //preRow:上一行(i+1行)的颜色 //curRow:当前行的颜色 private int dfs(int i,int j,int preRow,int curRow){ //如果所有格子都已涂色，说明找到了一个方案 if(i==0) return 1; //如果i行已涂色，开始对i-1行涂色，当前行作为下一个递归的前一行 if(j==3) return dfs(i-1,0,curRow,0); //参数压缩到一个int中 //int中的存储格式：当前行号+当前列号+上一行所填颜色+当前行所填颜色 //i不知道多少行，所以右移14位放最前面 //j取值为012，占两个比特位 //preRow和curRow均占2×3个比特位 int key=(i<<14)|(j<<12)|(preRow<<6)|curRow; //先往备忘录里瞅瞅 if(memo.containsKey(key)) return memo.get(key); int ret=0; //枚举(i,j)的颜色color for(int color=0;color<3;color++){ //不能和下面相邻格子(i+1,j)颜色相同 //preRow>0:先判断下一行是否有数据，有的话就要保证颜色不能相同 //(preRow>>(j*2)&3)：将需要比较的颜色从里面移动到最右边再用|提取出来 //preRow存储格式：最右侧颜色标识数+中间颜色标识数+最左侧标识数 //&3：将需要比较的颜色标识数移动到最右边后，用3（二进制11）来提取出颜色 if(preRow>0&&color==(preRow>>(j*2)&3)|| //不能和左侧相邻格子(i,j-1)颜色相同 j>0&&color==(curRow>>((j-1)*2)&3)) continue; //此行还未填完，因此preRow保持不变，把当前color存入当前行curRow的对应位置 ret=(ret+dfs(i,j+1,preRow,curRow|(color<<(j*2))))%MOD; } memo.put(key,ret);//存进备忘录 return ret; } }