今天继续推进leetcode上动态规划的部分题目，完成了“矩阵类型”。今天在做题的时候开了IDE，创建了一个github仓库，同时同步题解和思路，本文即主要由当时记录的思路集合而来。
62. 不同路径
引路题，因为从左上到右下，只能向右或向下且一次只能一步，因此可用排列组合来解。
动态规划的思路：构建二维dp数组，dp的值代表到达该位置的不同路径数目，边缘状态都是1，只有一条道直达；其他地方有两个选择，直接用两个选择所对应的dp的值相加。
64. 最小路径和
在前一道题目上进阶，从将网格变得“有权”。
先构建二维的dp数组，dp对应位置的值，即为到达该位置的最小路径。
再初始化边缘状态，因为边缘状态只有一条路能到，因此更新对应的dp值，只用前一个（0行即左一列，0列即上一排）dp值加上本格权重。
迭代非边缘状态时，用左一格权重+上一格权重即可。
~~实际上这两道是之前解出来的，当时没有记录。这儿与下931的处理不同，931要凸显“抵达前”费用，这里对应位置直接标上抵达后费用，我想原因在于，本题目的起点是固定的，路径被选择后抵达某格子支付的费用也是固定的；而931中，~~好吧测了下，不使用我所谓“抵达前”费用，亦可得出正确解
63. 不同路径II
在不同路径问题升级而来，一开始先初始化dp数组。dp
\[row\]\[col\]代表到达\(row, col\)位置的最多路径条数。
第二步判断起始位置和终点有没有障碍物堵上，堵上则直接返回（给出的障碍物范围是任意网格所有位置）。
第三步，动态规划进入dp数组的迭代，目的是更新dp，如果该位置上有障碍物直接dp
\[row\]\[col\]=0，判断下一个位置。
边缘位置时，由于机器人只能向右和向下运动，意味着边缘若有障碍物，则该行（列）后续dp值都将为0。
非边缘位置时，dp值为同行左一格dp值+同列上一格dp值（dp
\[row\]\[col\]= dp
\[row-1\]\[col\]+ dp
\[row\]\[col-1\]）。
一开始觉得容易做，不断出错最后改花了不少时间。
120. 三角形最小路径和
将三角形映射到矩形网格中，同样的处理方法，三角形特殊的一点在于这儿只能往下一行，下一行的同列或列+1位置，意味着三角形右侧的边需要特殊处理（没有从同一列直接向下一行的路径）。
第一步初始化dp数组，dp的值代表到达该位置的最小路径。
第二步处理边缘状态（左侧边，即dp
\[i\]\[0\]），只能一条路径下来，同样值就从上加下来即可。
第三步动态规划，从（1，1）位置开始遍历，但右侧边缘的位置，即dp
\[i\]\[len(dp\[i\])-1]的值需要单独处理。转移方程：
$$ dp[i][j] = min(dp[i-1][j]+triangle[i][j], dp[i-1][j-1]+triangle[i][j]) $$进阶——只使用O(n)空间
你可以只使用
O(n)的额外空间（n为三角形的总行数）来解决这个问题吗？
进阶只要求使用O(n)，但特殊的是，该三角形每行的元素数，等于行数。每行的dp值只取决于上一行，又最大长度行即为n，所以不难解。
要注意的是，每行内的遍历从要右向左，因为每行的值是取决于上一行同列以及上一行同列左侧一个的值，从左向右更新一维dp数组的话，左侧值被更新了，后续就没法用了。
错误了几次，在debug中走过来的，主要犯错在更新两个边的dp[j]
931. 下降路径的最小和
此类求解最小路径动态规划，构建dp数组时，凸显一个“抵达前费用”。比较容易，套范式即可解决。
第一步，构建并初始化二维dp数组（有m+1行，0行全0因为可以随意指定出发点）。每个位置的dp值代表的含义是：抵达该格前，最小的路径和。
第二步，遍历dp数组，根据转移方程更新状态，同时考虑边界状态即可。
第三步，求出m+1行最小值。
221. 最大正方形
本身不难，重点在于是是否知道该类题目的状态转移方程构造的方法。
第一步，初始化二维int型dp数组（切片），其中dp值表示含义为，以该格为右下角顶点，最大的正方形边长。
第二步，初始化边缘状态，即对0行和0列进行赋值，如果为0字符，则对应位置dp数组赋值为0，1字符则赋值为1.
第三步，根据状态转移方程，迭代。从（1，1）位置开始，若当前位置为0字符，则必定构成不了正方形，直接赋值dp数组对应位置值为0；若为1，则考虑能构建边长为多长的正方形，由（i-1，j）、（i-1，j-1）、（i，j-1）三者共同确定，由三者中最小值+1。推导过程略了