算法知识-从递归入手二维动态规划

一.二维动态规划1.什么是二维动态规划尝试函数有一个可变参数可以完全决定返回值进而可以改出1维动态规划的实现同理尝试函数有两个可变参数可以完全决定返回值那么就可以改出2维动态规划的实现一定要看看可变参数能否决定返回值2.二维动态规划解题过程一维二维三维甚至更多维动态规划问题大致过程都是写出尝试递归记忆化搜索(从顶到底的动态规划)严格位置依赖的动态规划(从底到顶的动态规划)空间时间的更多优化3.动态规划表的大小每个可变参数的最大值相乘4.动态规划的时间复杂度动态规划表的大小*每个格子枚举的代价5.二维动态规划整理依赖关系二维动态规划依然需要去整理动态规划表的格子之间的依赖关系找依赖关系往往通过画图来建立空间感使其更显而易见然后依然是从简单格子填写到复杂格子的过程即严格位置依赖的动态规划(从底到顶)6.空间压缩二维动态规划的压缩空间技巧原理不难会了之后前篇一律但是不同题目的依赖关系不一样需要很细心的画图来整理具体题目的依赖关系最后进行空间压缩实现二.例题1.LCR 099. 最小路径和 - 力扣LeetCode算最小路径和一个机器人每次只能向下或者向右移动一步我们设f(i,j)表示(0,0)到(i,j)的最小路径和他能从它的上面和左面转移过来代码如下int f(int i,int j,vectorvectorint grid,vectorvectorint dp){ if(i0j0){ return grid[0][0]; } if(dp[i][j]!-1){ return dp[i][j]; } int ansINT_MAX; if(i-10){ ansmin(ans,f(i-1,j,grid,dp)grid[i][j]); } if(j-10){ ansmin(ans,f(i,j-1,grid,dp)grid[i][j]); } dp[i][j]ans; return dp[i][j]; } int f1(vectorvectorint grid){ int ngrid.size(),mgrid[0].size(); auto dpvector(n,vectorint(m,INT_MAX)); dp[0][0]grid[0][0]; for(int i0;in;i){ for(int j0;jm;j){ if(i-10){ dp[i][j]min(dp[i][j],dp[i-1][j]grid[i][j]); } if(j-10){ dp[i][j]min(dp[i][j],dp[i][j-1]grid[i][j]); } } } return dp[n-1][m-1]; }我们通过观察发现计算过程中我们只需要前一行和当前行就可以完成这个计算过程并且我们最后也只是想求得dp[n-1][m-1]所以我们可以进行空间的压缩把二维数组压缩成两个数组我们可以使用两个数组的滚动更新但是最终版本为一个一维数组的自我更新int f2(vectorvectorint grid){ int mgrid[0].size(); int ngrid.size(); vectorintdp(m,0); dp[0]grid[0][0]; //想象的dp表中的第0行的数据 for(int i1;im;i){ dp[i]dp[i-1]grid[0][i]; } //枚举第1行到第n-1行 for(int i1;in;i){ //i1想象中的表的第一行数据 dp[0]grid[i][0]; for(int j1;jm;j){ dp[j]min(dp[j-1],dp[j])grid[i][j]; } } return dp[m-1]; }想象中的dp表的第零行数据就是从它的前一个转移过来的(dp[i]dp[i-1]grid[0][i])之后我们枚举第一行到第n-1行每一行的第0列一定是从上一行的第一列转移过来也就是dp[0],之后再加上grid值之后我们枚举第一列到第m-1列我们在枚举过程中枚举过的列会变为第i行的对应列的dp表的值(当前位置的左)之后没有枚举过的列还是第i-1行(当前位置的上)对应列的值所以我们在枚举到第j列时j-1也就是第i行j-1列的dp表的值j是第i-1行第j列的dp表的值所以就是一个上方一个左方进行状态转移。三.不适合改动态规划1.特征能改成动态规划的递归统一特征决定返回值的可变参数类型往往都比较简单一般不会比int类型更复杂为什么如下例题决定返回值的不仅仅是几个int由于相同的点不能反复走我们在过程中修改了char二维数组二维数组的状态有很多所以这样的题目不适合改动态规划这个角度可以解释带路径的递归(可变参数类型复杂)不适合或者说没有必要改成动态规划不用改成动态规划的递归往往数据量都不大本身就是希望你写暴力递归不管是几维动态规划经常从递归的定义出发避免后续进行很多边界讨论2.无法改成动态规划的例题79. 单词搜索 - 力扣LeetCodeclass Solution { public: bool traceback(int row,int col,vectorvectorchar board,string word,int k){ if(kword.size())return true; if(word.size()0||rowboard.size()||row0||colboard[0].size()||col0||board[row][col]!word[k]){ return false; } char tmpboard[row][col]; board[row][col]0; bool anstraceback(row1,col,board,word,k1)|| traceback(row-1,col,board,word,k1)||traceback(row,col-1,board,word,k1) ||traceback(row,col1,board,word,k1); board[row][col]tmp; return ans; } bool exist(vectorvectorchar board, string word) { for(int i0;iboard.size();i){ for(int j0;jboard[0].size();j){ if(traceback(i,j,board,word,0))return true; } } return false; } };决定返回值的不仅仅是参数列表中的三个参数不同的路径到达(i,j,k)这一个状态返回值可能不同所以决定返回值的还有还有二维矩阵的修改状况但是二维矩阵的修改状态过多动态规划的时间复杂度是动态规划表的大小乘每个格子的枚举的代价所以时间复杂度过高不能改成动态规划也是不存在大量重复调用改成动态规划没有意义四.更多例题入手二维动态规划1.LCR 095. 最长公共子序列 - 力扣LeetCode我们首先明确状态:f(len1,len2)text1,从0开始len1长度text2从0开始len2长度两个字符串的最长公共子序列决策方案:(1)选s[len-1]和t[len2-1],如果两个位置的字符相等那么他一定是最优的答案就是这个,ansf(len1-1,len2-1)1(2)选s[len1-1]不选t[len2-1],ansf(len1-1,len2)(3)不选s[len1-1],选t[len2-1],ansf(len1,len2-1)(4)两者都不选一定是最差的解一定不如(2)(3)所以不用考虑1.记忆化搜索int f(int len1,int len2,string s1,string s2,vectorvectorintdp){ if(len10||len20){ return 0; } if(dp[len1][len2]!-1){ return dp[len1][len2]; } int ans0; //如果能两个都选 if(s1[len1-1]s2[len2-1]){ ansf(len1-1,len2-1,s1,s2,dp)1; }else{ ansmax(f(len1-1,len2,s1,s2,dp),f(len1,len2-1,s1,s2,dp)); } dp[len1][len2]ans; return ans; }2.严格位置依赖的动态规划我们画图分析发现每个格子依赖它的左它的上和它的左上所以我们for循环的大方向是从上到下从左向右这样就可以保证来到某个格子它的左上左上已经被求过了。对于初始值当len10时那么s1是空串最长公共子序列为0当len20那么s2是空串最长公共子序列为0所以dp表中的第0行和第0列的初始值为0int f2(string s1,string s2){ int ns1.size(),ms2.size(); vectorvectorintdp(n1,vectorint(m1,0)); for(int j0;jm;j){ dp[0][j]0; } for(int len11;len1n;len1){ dp[len1][0]0; for(int len21;len2m;len2){ if(s1[len1-1]s2[len2-1]){ dp[len1][len2]dp[len1-1][len2-1]1; }else{ dp[len1][len2]max(dp[len1-1][len2],dp[len1][len2-1]); } } } return dp[n][m]; }3.空间压缩int f3(strings1,string s2){ //s1作为大的字符串,我们让长度较小的作为列这样可以节省空间 if(s1.size()s2.size()){ swap(s1,s2); } int ns1.size(),ms2.size(); vectorintdp(m1,0); int leftUp0; for(int len11;len1n;len1){ leftUp0; for(int len21;len2m;len2){ int tmpdp[len2]; if(s1[len1-1]s2[len2-1]){ dp[len2]leftUp1; }else{ dp[len2]max(dp[len2],dp[len2-1]); } leftUptmp; } } return dp[m]; }首先我们可以把一个二维数组压缩成一维数组所以我们选择字符串长度小的作为列这样可以让一维数组的大小更小之后在更新过程中dp[len2-1]已经被更新了所以是len1行的dp[len2-1],也就是它的左之后当前的dp[len2]还没更新所以他是len1-1行的dp[len2]也就是它的上但是它的左上数组中无法保存我们可以使用一个变量leftUp来更新2.516. 最长回文子序列 - 力扣LeetCode方法一:一个串的最长回文子序列就是它和它的反转串的最长公共子序列//方法一:最长回文子序列就是原串和它的反转串的最长公共子序列 int f3(strings1,string s2){ //s1作为大的字符串,我们让长度较小的作为列这样可以节省空间 if(s1.size()s2.size()){ swap(s1,s2); } int ns1.size(),ms2.size(); vectorintdp(m1,0); int leftUp0; for(int len11;len1n;len1){ leftUp0; for(int len21;len2m;len2){ int tmpdp[len2]; if(s1[len1-1]s2[len2-1]){ dp[len2]leftUp1; }else{ dp[len2]max(dp[len2],dp[len2-1]); } leftUptmp; } } return dp[m]; } int longestPalindromeSubseq(string s) { string s1s; reverse(s.begin(),s.end()); return f3(s,s1); }方法二:重新设计状态状态:f(i,j)表示s字符串的[0,...i]与[j,...n-1]的最长回文子序列有多长basecase:(1)ij,ans1(2)ji1,如果s[i]s[j],那么ans1否则ans0(由于我们状态转移会移动两个单位所以需要这个basecase)决策方案:(1)选s[i]和s[j],前提是s[i]s[j],那么一定是最优秀的解ansf(i1,j-1)1(2)选s[i],不选s[j],ansf(i1,j)(3)不选s[i],选s[j],ansf(i,j1)(4)都不选一定没有(2),(3)优秀1.记忆化搜索int f(int i,int j,strings,vectorvectorintdp){ if(ij)return 1; if(ji1){ return s[i]s[j]?2:1; } if(dp[i][j]!-1){ return dp[i][j]; } int ans0; //决策方案 if(s[i]s[j]){ ansf(i1,j-1,s,dp)2; }else{ ansmax(f(i1,j,s,dp),f(i,j-1,s,dp)); } dp[i][j]ans; return ans; }2.严格位置依赖的动态规划通过画图发现所有lr的位置都是非法的格子,之后一个格子需要它的左它的下和它的左下所以我们遍历的大方向是从下到上从左到右之后对于lr为位置最长回文子序列为1如果rl1,那么判断s[l]s[r]如果相等那么最长回文子序列为2否则为1//严格位置依赖的动态规划 int f1(string s){ int ns.size(); vectorvectorintdp(n,vectorint(n,1)); for(int in-2;i0;i--){ dp[i][i1]s[i]s[i1]?2:1; for(int ji2;jn;j){ if(s[i]s[j]){ dp[i][j]dp[i1][j-1]2; }else{ dp[i][j]max(dp[i1][j],dp[i][j-1]); } } } return dp[0][n-1]; }3.空间压缩和之前的题目一样就是它的左是dp[j-1]已经转移完了是当前行的dp[j-1],它的下是dp[j],是还没转移完的是i1行的dp[j],是它的下之后它的左下没法保存所以需要一个变量保存//状态压缩 int f2(string s){ int ns.size(); vectorintdp(n,1); int leftDown1; for(int in-2;i0;i--){ leftDown1; dp[i1]s[i]s[i1]?2:1; for(int ji2;jn;j){ int tmpdp[j]; if(s[i]s[j]){ dp[j]leftDown2; }else{ dp[j]max(dp[j],dp[j-1]); } leftDowntmp; } } return dp[n-1]; }(1)题目一115. 不同的子序列 - 力扣LeetCode我们首先先明确状态用两个参数ij(i表示字符串s的前缀长度j表示字符串t的前缀长度)我们还是用之前那种很常用的讨论方式s[i-1]选与不选如果不选s[i-1],那么我们就去看s前缀长度为i-2与t的前缀长度j有多少种匹配方案也就是f(i-1,j)之后我们如果选s[i-1]选s[i-1],匹配到t的前缀长度为j那么一定是s[i-1]与t[j-1]匹配才能选s[i-1],之后加上字符串s前缀长度为i-1字符串t前缀长度为t-1也就是f(i-1,j-1),对于basecase如果i为0说明s为0那么如果t从1....m那么都不可能选出就是0如果j为0也就是t的长度为0我们都不选空串有一种方案1.记忆化搜索int f(int i,int j,string s,string t,vectorvectorintdp){ if(j0){ return 1; } if(i0){ return 0; } if(dp[i][j]!-1){ return dp[i][j]; } int ansf(i-1,j,s,t,dp); if(s[i-1]t[j-1]){ ans(f(i-1,j-1,s,t,dp)); } dp[i][j]ans; return ans; }2.关系依赖的动态规划int f1(string s,string t){ int ns.size(),mt.size(); auto dpvector(n1,vectorunsigned(m1,0)); for(int i0;in;i){ dp[i][0]1; } for(int i1;in;i){ for(int j1;jm;j){ dp[i][j]dp[i-1][j]; if(s[i-1]t[j-1]){ dp[i][j]dp[i-1][j-1]; } } } return dp[n][m]; }3.空间压缩int f2(string s,string t){ int ns.size(),mt.size(); vectorunsigneddp(m1,0); dp[0]1; for(int i1;in;i){ for(int jm;j1;j--){ if(s[i-1]t[j-1]){ dp[j]dp[j-1]; } } } return dp[m]; }对于空间压缩每一个格子取决于它的上一个格子和它的左上角的格子我们从上往下遍历那么得到上一行的dp表中的格子之后从右往左遍历那么左上角就会被保留下来实现自我更新(2)题目二72. 编辑距离 - 力扣LeetCode首先状态f(i,j)表示(s[0....i-1] ,t[0....j-1])有s转换成t的最少操作次数(1)s[i-1]参与{a.s[i-1]变成t[j-1]{1.s[i-1]t[j-1] 代价为0计算s[0...i-2],t[0...j-2]f(i-1,j-1)2.s[i-1]!t[j-1] 代价为c(替换)计算s[0...i-2],t[0...j-2],f(i-1,j-1)c}b.s[i-1]不去变成t[j-1](这个题目和一般题目不同我们可以通过插入的方式去凑最后一个字符) {s[0....i-1]-t[0...j-2],最后再插入一个字符f(i,j-1)a}}(2)s[i-1]不参与s[0....i-2]-s[0....j-1]再加上删除s[i-1]的代价f(i-1,j)b之后最有代价取最小basecasei0说明源字符串长度为0要是想要变成长度为j的目标字符串需要添加j个字符添加代价为aa*jj0说明目标字符串长度为0要是想要变成目标字符串需要删除i个字符删除代价为bb*i1.记忆化搜索int f(int i,int j,string s,string t,int a,int b,int c,vectorvectorintdp){ if(i0){ return a*j; } if(j0){ return b*i; } if(dp[i][j]!-1){ return dp[i][j]; } //s[i-1]一定参与 //a:s[i-1]变成t[j-1] //1.s[i-1]t[j-1] int ansf(i-1,j-1,s,t,a,b,c,dp); if(s[i-1]!t[j-1]){ //不等需要加上替换 ansc; } //b:s[0...i-1]对应t[0...j-2] ansmin(ans,f(i,j-1,s,t,a,b,c,dp)a); //s[i-1]不参与 //s[0...i-2]对应t[0...j-1] ansmin(ans,f(i-1,j,s,t,a,b,c,dp)b); dp[i][j]ans; return ans; }2.基于依赖的动态规划int f1(string s,string t,int a,int b,int c){ int ns.size(),mt.size(); auto dpvector(n1,vectorint(m1,0)); for(int j0;jm;j){ dp[0][j]a*j; } for(int i0;in;i){ dp[i][0]b*i; } for(int i1;in;i){ for(int j1;jm;j){ dp[i][j]dp[i-1][j-1]; if(s[i-1]!t[j-1]){ //不等需要加上替换 dp[i][j]c; } //b:s[0...i-1]对应t[0...j-2] dp[i][j]min(dp[i][j],dp[i][j-1]a); //s[i-1]不参与 //s[0...i-2]对应t[0...j-1] dp[i][j]min(dp[i][j],dp[i-1][j]b); } } return dp[n][m]; }3.空间压缩int f2(string s,string t,int a,int b,int c){ int ns.size(),mt.size(); vectorintdp(m1,0); for(int j0;jm;j){ dp[j]a*j; } int leftup0,back0; for(int i1;in;i){ dp[0]b*i; leftup(i-1)*b; for(int j1;jm;j){ backdp[j]; dp[j]leftup; if(s[i-1]!t[j-1]){ //不等需要加上替换 dp[j]c; } //b:s[0...i-1]对应t[0...j-2] dp[j]min(dp[j],dp[j-1]a); //s[i-1]不参与 //s[0...i-2]对应t[0...j-1] dp[j]min(dp[j],backb); leftupback; } } return dp[m]; }我们发现每个位置依赖左依赖上依赖左上。我们从上往下遍历从左往右遍历记录leftup