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

一.基础尝试函数有1个可变参数可以决定返回值进而可以改出1维动态规划表的表现尝试函数有2个可变参数可以决定返回值进而可以改出2维动态规划表的表现尝试函数有3个可变参数可以决定返回值进而可以改出3维动态规划表的表现大体过程都是:写出尝试递归记忆化搜索严格位置依赖的动态规划空间时间的更多优化二.例题1.题目一首先分析状态:f(i,m,n):表示[i...n-1]自由选择保证0个数不超过m个1的个数不超过n个最多选择多少个字符串basecase:is.size(),此时已经选择到了最末尾能选择0个字符串决策方案:(1)不选当前位置:f(i1,m,n)(2)选当前位置:f(i1,m-zero,n-one)(1)记忆化搜索void get_zo(string s,int zero,int one){ for(autoc:s){ if(c0)zero; if(c1)one; } } //f(i,m,n):表示[i...n-1]自由选择保证0的个数不超过m1的个数不超过n //最多能选择多少个字符串 //决策方案:当前位置选与不选 int f(int i,int m,int n,vectorstringstrs,vectorvectorvectorintdp){ if(istrs.size()){ return 0; } if(dp[i][m][n]!-1){ return dp[i][m][n]; } int zero0,one0; get_zo(strs[i],zero,one); int ans; //决策方案1不选当前位置 ansf(i1,m,n,strs,dp); //决策方案2选当前位置 if(zeromonen){ ansmax(ans,f(i1,m-zero,n-one,strs,dp)1); } dp[i][m][n]ans; return ans; }(2)严格位置依赖的动态规划通过画图分析发现每个位置只依赖它的上一层元素所以我们只需要从上往下枚举剩下两层循环顺序无所谓int f1(vectorstring strs, int m, int n){ int lenstrs.size(); vectorvectorvectorintdp(len1,vectorvectorint(m1,vectorint(n1,0))); for(int ilen-1;i0;i--){ for(int j0;jm;j){ for(int k0;kn;k){ int zero0,one0; get_zo(strs[i],zero,one); //决策方案1不选当前位置 dp[i][j][k]dp[i1][j][k]; //决策方案2选当前位置 if(zerojonek){ dp[i][j][k]max(dp[i][j][k],dp[i1][j-zero][k-one]1); } } } } return dp[0][m][n]; }(3)空间压缩由于我们刚才分析了每个位置只依赖它的上一层元素所以我们只需要维护两个二维数组(一个数组作为它的上一层一个数组作为当前层)让它滚动下去即可int f2(vectorstring strs, int m, int n){ int lenstrs.size(); vectorvectorintlast(m1,vectorint(n1,0)), cur(m1,vectorint(n1,0)); for(int ilen-1;i0;i--){ for(int j0;jm;j){ for(int k0;kn;k){ int zero0,one0; get_zo(strs[i],zero,one); //决策方案1不选当前位置 cur[j][k]last[j][k]; //决策方案2选当前位置 if(zerojonek){ cur[j][k]max(cur[j][k],last[j-zero][k-one]1); } } } lastcur; } return cur[m][n]; }2.题目二状态:f(i,r,p):表示从[i,...n-1]:还剩余r名员工还差p个利润能有多少种选择决策方案:(1)不选则当前工作,ansf(i1,r,p)(2)选择当前工作,在r-group[i]0情况下ansansf(i1,r-group[i],max(0,p-porfit[i]))注意这里有p-porfit[i]和0取大因为我们尽量不希望我们的状态小于零如果小于零和等于零效果一样的话因为我们后续需要改严格位置依赖的动态规划(1)记忆化搜索int f(int i,int r,int p,vectorintgroup,vectorintprofit,vectorvectorvectorintdp){ //如果选到末尾了 if(igroup.size()){ return p0?1:0; } if(dp[i][r][p]!-1){ return dp[i][r][p]; } //决策方案: //(1)不选择 int ans0; ans(ansf(i1,r,p,group,profit,dp))%mod; //(2)选择 if(r-group[i]0){ //注意我们这里尽量不想让可变参数变为负数如果零和负数效果一样的话 ans(ansf(i1,r-group[i],max(0,p-profit[i]),group,profit,dp))%mod; } dp[i][r][p]ans; return ans%mod; }(2)严格位置依赖的动态规划通过分析发现每一层还是仅仅依赖它的上一层所以依旧是从上往下枚举其他两层循环随意int f1(int n, int minProfit, vectorint group, vectorint profit ){ int lengroup.size(); vectorvectorvectorintdp(len1,vectorvectorint(n1,vectorint(minProfit1,0))); for(int r0;rn;r){ dp[len][r][0]1; } for(int ilen-1;i0;i--){ for(int j0;jn;j){ for(int k0;kminProfit;k){ //决策方案: //(1)不选择 dp[i][j][k]dp[i1][j][k]; //(2)选择 if(j-group[i]0){ //注意我们这里尽量不想让可变参数变为负数如果零和负数效果一样的话 dp[i][j][k](dp[i][j][k]dp[i1][j-group[i]][max(k-profit[i],0)])%mod; } } } } return dp[0][n][minProfit]; }(3)空间压缩和上一题思路一致int f2(int n, int minProfit, vectorint group, vectorint profit ){ int lengroup.size(); vectorvectorintlast(n1,vectorint(minProfit1,0)),cur(n1,vectorint(minProfit1,0)); for(int r0;rn;r){ last[r][0]1; } for(int ilen-1;i0;i--){ for(int j0;jn;j){ for(int k0;kminProfit;k){ //决策方案: //(1)不选择 cur[j][k]last[j][k]; //(2)选择 if(j-group[i]0){ //注意我们这里尽量不想让可变参数变为负数如果零和负数效果一样的话 cur[j][k](cur[j][k]last[j-group[i]][max(k-profit[i],0)])%mod; } } } lastcur; } return cur[n][minProfit]; }3.题目三状态f(i,j,k):表示当前来到i,j位置还剩k步还留在棋盘上的概率决策方案:向八个方向转移,每个方向概率/8之后在累加basecase:如果越界概率为0没越界之后k为0概率为1vectorpairint,intdir{{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; double f(int i,int j,int k,int n,vectorvectorvectordoubledp){ //basecase if(i0||j0||in||jn){ return 0; } if(k0){ return 1; } if(dp[i][j][k]!-1){ return dp[i][j][k]; } double ans0; for(auto[dx,dy]:dir){ ansf(idx,jdy,k-1,n,dp)/8; } dp[i][j][k]ans; return ans; }4.题目四能够被k整除我们可以转换为累加和%k0,我们这里不去设计累加和作为状态因为累加和个数太多了而k的范围50状态:f(i,j,k):表示从(i,j)位置出发累加和%kr的路径个数有多少个决策方案:首先我们选择当前数并且知道当前需要的余数是r我们需要算出选择当前数后续需要的余数是什么?(kr-(当前数%k))%k(1)向下转移(2)向右转移basecase:in-1jm-1grid[i][j]%kr?1:0;(1)记忆化搜索//f(i,j,k)表示从(i,j)出发整体的累加和%k的结果是r int f(vectorvectorintgrid,int k,int i,int j,int r,vectorvectorvectorintdp){ if(igrid.size()-1jgrid[0].size()-1){ return grid[i][j]%kr?1:0; } if(dp[i][j][r]!-1){ return dp[i][j][r]; } //决策方案 int need(r-(grid[i][j]%k)k)%k; int ans0; if(j1grid[0].size()) ansf(grid,k,i,j1,need,dp); if(i1grid.size()) ans(ansf(grid,k,i1,j,need,dp))%mod; dp[i][j][r]ans; return ans%mod; }