二维型
二维型
Unique Paths
状态：f[i][j]表示到坐标i,j位置的方案数
转移：f[i][j]=f[i-1][j]+f[i][j-1]
边界：f[0][0]=1
Unique Paths II
有些各自有障碍物，不能通过
状态：f[i][j]表示到坐标i,j位置的方案数
转移：f[i][j]=f[i-1][j]+f[i][j-1], 0|g[i][j]==1
边界：f[0][0]=1
Minimum Path Sum
(0,0)到(m-1,n-1)的最小花费
状态：f[i][j]表示到坐标i,j位置的最小花费
转移：f[i][j]=min{f[i-1][j], f[i][j-1]}+A[i][j]
边界：f[0][j], f[i][0]
空间优化：如果只依赖于前面的k列，则可以滚动数组
Triangle 数字三角形
状态：f[i][j]表示到坐标i,j位置的最小花费
转移：f[i][j]=min{f[i-1][j],f[i][j-1]}+a[i][j]
边界：f[0][0]=a[0][0]
答案：min{f[n-1][j]}
Maximal Square 全1正方形
求一个01矩阵中，全为1的正方形个数
状态：
f[i][j]表示到坐标i,j位置的方案数left[i][j]表示i,j往左连续的1最长多长up[i][j]表示i,j往上连续的1最长多长
转移：
0|m[i][j]==0
left[i][j]=left[i][j-1]+1up[i][j]=up[i-1][j]+1f[i][j]=min{up[i-1][j], left[i][j-1], f[i-1][j-1]}+1
边界：
d[i][0],left[i][0],up[i][0]=m[i][0]d[0][j],left[0][j],up[0][j=m[0][j]
答案：sum{dp[i][j]}
滚动数组，滚i，开2大小，答案在计算dp数组的时候累计
Maximal Square II
找最大的对角线全1其他都0的正方形
Knight Shortest Paths II
只能向右面的 4 个方向跳，求左上到右下最短路径
状态：f[i][j]表示到坐标i,j位置的最小步数
转移：min{f[i-][j-]}
边界：f[i][j]=inf,f[0][0]=0
答案：f[n-1][m-1]
逆向
矩阵的终点的状态已知，起点状态为止，求起点状态
174 地下城游戏
状态：f[i][j]表示从i,j到n-1,m-1的最小HP
转移：f[i][j]=max{1,max{f[i+1][j],f[i][j+1]}-grid[i][j]}
边界：f[n][i]=inf,f[n][m-1]=1
答案：f[0][0]
1444 Number of Ways of Cutting a Pizza
状态：f[k][i][j]表示切k刀从i,j到n-1,m-1的方案数
转移：f[k][i][j]=sum{f[k-1][i][j2]}+sum{f[k-1][i2][j]}
边界：f[0][i][j]=1,sufSum(i,j)>0
答案：f[k][0][0]
子矩阵
从子串型延展的，依然 Kadane 算法
3148 矩阵中的最大得分
状态：f[i][j]表示以坐标i,j结尾的最大分数
转移：f[i][j]=grid[i][j]+Math.max(Math.max(0,f[i-1][j])-grid[i-1][j], Math.max(0,f[i][j-1])-grid[i][j-1])
答案：max{f[i][j]}
统计全为 1 的正方形子矩阵
状态：
限制
背包型
lc1235 矩阵中和能被 K 整除的路径
状态：f[i][j][k]表示以坐标i,j结尾余数为k的路径数量
转移：f[i][j][(k + grid[i][j]%k)]=(f[i-1][j][k]+f[i][j-1][k])%mod
答案：f[m-1][n-1][0]
从递归入手二维动态规划
动态规划表的大小：每个可变参数的可能性数量相乘
动态规划方法的时间复杂度：动态规划表的大小*每个格子的枚举代价
二维动态规划依然需要去整理动态规划表的格子之间的依赖关系
找寻依赖关系，往往通过画图来建立空间感，使其更显而易见
然后依然是从简单格子填写到复杂格子的过程，即严格位置依赖的动态规划（从底到顶）
二维动态规划的压缩空间技巧原理不难，会了之后千篇一律
但是不同题目依赖关系不一样，需要很细心的画图来整理具体题目的依赖关系
最后进行空间压缩的实现
俯改成动态规划的速归，统一特征：
决定返回值的可变参数类型往往都比较简单，一般不会比1t类型更复杂。为什么？
eg. 单词搜索这个题，决定返回值的，不仅是左边 i, j, idx 还有board哪里被访问过的一个seen二维数组（这个可以用状压，但是没必要）
从这个角度，可以解释带路径的递归（可变参数类型复杂），不适合或者说没有必要改成动态规划
题目2就是说明这一点的
不管几维动态规划
经常从递归的定义出发，避免后续进行很多边界讨论
这需要一定的经验来预知
带路径的递归不适合改dp