算法题打卡-二维动态规划

62. 不同路径路径数量二维dp数组的定义已经在题目中显式给出简单。可以压缩成一维dp数组懒不想压了。classSolution{public:/* dp[i][j] 到达i行j列的路径数量 */intuniquePaths(intm,intn){vectorvectorintdp(m,vectorint(n,0));for(inti0;im;i)dp[i][0]1;for(intj0;jn;j)dp[0][j]1;for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}};64. 最小路径和没什么需要特别注意的。classSolution{public:/* dp[i][j] 到达网格i行j列的最小数字和 */intminPathSum(vectorvectorintgrid){intmgrid.size(),ngrid[0].size();vectorvectorintdp(m,vectorint(n,0));dp[0][0]grid[0][0];for(inti1;im;i)dp[i][0]grid[i][0]dp[i-1][0];for(intj1;jn;j)dp[0][j]grid[0][j]dp[0][j-1];for(inti1;im;i){for(intj1;jn;j){intcostgrid[i][j];dp[i][j]costmin(dp[i-1][j],dp[i][j-1]);}}returndp[m-1][n-1];}};1143. 最长公共子序列本题让我对状态转移又有了新的理解当前比较字符串abc和abc ! b所以最长公共子序列的结果是max(ab与ababc与a)。我自己在考虑时匹配成功的结果是dp[i][j]匹配不成功时就想不到如何利用前一个状态了。无法继续的原因是匹配后没有利用上一个状态做转移而是粗暴地给dp[i][j]在初始值基础上去加一。当前比较c1和c2的结果已知如果都满足加一是对的给谁加一给去掉c1和c2的两字符串比较结果加一。基于这个逻辑c1≠c2的处理逻辑就很好处理了在t1-c1t2和t1t2 - c2中取更大值。classSolution{public:/* dp[i][j]: text1在0-i与text2在0-j的最长公共子序列长度 */intlongestCommonSubsequence(string text1,string text2){intlen1text1.length(),len2text2.length();vectorvectorintdp(len11,vectorint(len21,0));for(inti1;ilen1;i){charc1text1.at(i-1);for(intj1;jlen2;j){charc2text2.at(j-1);if(c1c2)dp[i][j]dp[i-1][j-1]1;elsedp[i][j]max(dp[i-1][j],dp[i][j-1]);}}returndp[len1][len2];}};72. 编辑距离很有趣的一道题运用1143解法的方式很巧妙出处参考力扣题解这里我把自己的思考过程写下来。对于word1 “hosre”, word2 “ros”以dp[1][1]的求解为例dp[1][1] h到r的距离既然要设计状态转移我们来看左、上、左上分别是什么左 dp[1][0] “h到”的距离上 dp[0][1] 到r的距离左上 dp[0][0] “到”的距离接下来看可能的状态转移方程dp[1][1] 左 到r的距离 左 1dp[1][1] 上 “h到”的距离 上 1dp[1][1] 左上 h到r的距离 左上 1在上述三种方式中选择最小的即可。再看一个例子dp[2][2] ho到ro的距离左 dp[2][1] ho到r的距离上 dp[1][2] h到ro的距离左上 dp[1][1] h到r的距离可能的状态转移方程dp[2][2] 左 到o的距离 左 1dp[2][2] 上 “o到”的距离 上 1dp[2][2] 左上 o到o的距离 左上 0总结dp[i][j] 左 到c2的距离 左 1dp[i][j] 上 “c1到”的距离 上 1dp[i][j] 左上 c1到c2的距离若 c1 c2c1到c2的距离 0若 c1 ! c2c1到c2的距离 1dp[i][j]取上述三者最小值。classSolution{public:/* dp[i][j]将word1 [0,i)转换为word2 [0,j)需要的最少操作数 */intminDistance(string word1,string word2){intlen1word1.length(),len2word2.length();vectorvectorintdp(len11,vectorint(len21,0));for(inti0;ilen1;i)dp[i][0]i;for(intj0;jlen2;j)dp[0][j]j;for(inti1;ilen1;i){charc1word1.at(i-1);for(intj1;jlen2;j){charc2word2.at(j-1);intleftdp[i][j-1]1;intupdp[i-1][j]1;intleft_updp[i-1][j-1];if(c1!c2)left_up1;dp[i][j]min(left_up,min(left,up));}}returndp[len1][len2];}};