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

一.基础

尝试函数有1个可变参数可以决定返回值，进而可以改出1维动态规划表的表现

尝试函数有2个可变参数可以决定返回值，进而可以改出2维动态规划表的表现

尝试函数有3个可变参数可以决定返回值，进而可以改出3维动态规划表的表现

大体过程都是:

写出尝试递归

记忆化搜索

严格位置依赖的动态规划

空间，时间的更多优化

二.例题

1.题目一

首先分析状态:f(i,m,n):表示[i...n-1]自由选择，保证0个数不超过m个，1的个数不超过n个，最多选择多少个字符串

basecase:i==s.size(),此时已经选择到了最末尾，能选择0个字符串

决策方案:

(1)不选当前位置:f(i+1,m,n)

(2)选当前位置:f(i+1,m-zero,n-one)

(1)记忆化搜索

void get_zo(string &s,int &zero,int &one){ for(auto&c:s){ if(c=='0')zero++; if(c=='1')one++; } } //f(i,m,n):表示[i...n-1]自由选择，保证0的个数不超过m，1的个数不超过n //最多能选择多少个字符串 //决策方案:当前位置选与不选 int f(int i,int m,int n,vector<string>&strs,vector<vector<vector<int>>>&dp){ if(i==strs.size()){ return 0; } if(dp[i][m][n]!=-1){ return dp[i][m][n]; } int zero=0,one=0; get_zo(strs[i],zero,one); int ans; //决策方案1：不选当前位置 ans=f(i+1,m,n,strs,dp); //决策方案2：选当前位置 if(zero<=m&&one<=n){ ans=max(ans,f(i+1,m-zero,n-one,strs,dp)+1); } dp[i][m][n]=ans; return ans; }

(2)严格位置依赖的动态规划

通过画图分析发现，每个位置只依赖它的上一层元素，所以我们只需要从上往下枚举，剩下两层循环顺序无所谓

int f1(vector<string>& strs, int m, int n){ int len=strs.size(); vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1,0))); for(int i=len-1;i>=0;i--){ for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ int zero=0,one=0; get_zo(strs[i],zero,one); //决策方案1：不选当前位置 dp[i][j][k]=dp[i+1][j][k]; //决策方案2：选当前位置 if(zero<=j&&one<=k){ dp[i][j][k]=max(dp[i][j][k],dp[i+1][j-zero][k-one]+1); } } } } return dp[0][m][n]; }

(3)空间压缩

由于我们刚才分析了，每个位置只依赖它的上一层元素，所以我们只需要维护两个二维数组(一个数组作为它的上一层，一个数组作为当前层)，让它滚动下去即可

int f2(vector<string>& strs, int m, int n){ int len=strs.size(); vector<vector<int>>last(m+1,vector<int>(n+1,0)), cur(m+1,vector<int>(n+1,0)); for(int i=len-1;i>=0;i--){ for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ int zero=0,one=0; get_zo(strs[i],zero,one); //决策方案1：不选当前位置 cur[j][k]=last[j][k]; //决策方案2：选当前位置 if(zero<=j&&one<=k){ cur[j][k]=max(cur[j][k],last[j-zero][k-one]+1); } } } last=cur; } return cur[m][n]; }

2.题目二

状态:f(i,r,p):表示从[i,...n-1]:还剩余r名员工，还差p个利润，能有多少种选择

决策方案:

(1)不选则当前工作,ans=f(i+1,r,p)

(2)选择当前工作,在r-group[i]>=0情况下，ans=ans+f(i+1,r-group[i],max(0,p-porfit[i]))

注意这里有p-porfit[i]和0取大，因为我们尽量不希望我们的状态小于零，如果小于零和等于零效果一样的话，因为我们后续需要改严格位置依赖的动态规划

(1)记忆化搜索

int f(int i,int r,int p,vector<int>&group,vector<int>&profit,vector<vector<vector<int>>>&dp){ //如果选到末尾了 if(i==group.size()){ return p==0?1:0; } if(dp[i][r][p]!=-1){ return dp[i][r][p]; } //决策方案: //(1)不选择 int ans=0; ans=(ans+f(i+1,r,p,group,profit,dp))%mod; //(2)选择 if(r-group[i]>=0){ //注意我们这里尽量不想让可变参数变为负数，如果零和负数效果一样的话 ans=(ans+f(i+1,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, vector<int>& group, vector<int>& profit ){ int len=group.size(); vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(n+1,vector<int>(minProfit+1,0))); for(int r=0;r<=n;r++){ dp[len][r][0]=1; } for(int i=len-1;i>=0;i--){ for(int j=0;j<=n;j++){ for(int k=0;k<=minProfit;k++){ //决策方案: //(1)不选择 dp[i][j][k]=dp[i+1][j][k]; //(2)选择 if(j-group[i]>=0){ //注意我们这里尽量不想让可变参数变为负数，如果零和负数效果一样的话 dp[i][j][k]=(dp[i][j][k]+dp[i+1][j-group[i]][max(k-profit[i],0)])%mod; } } } } return dp[0][n][minProfit]; }

(3)空间压缩

和上一题思路一致

int f2(int n, int minProfit, vector<int>& group, vector<int>& profit ){ int len=group.size(); vector<vector<int>>last(n+1,vector<int>(minProfit+1,0)),cur(n+1,vector<int>(minProfit+1,0)); for(int r=0;r<=n;r++){ last[r][0]=1; } for(int i=len-1;i>=0;i--){ for(int j=0;j<=n;j++){ for(int k=0;k<=minProfit;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; } } } last=cur; } return cur[n][minProfit]; }

3.题目三

状态：f(i,j,k):表示当前来到i,j位置，还剩k步，还留在棋盘上的概率

决策方案:向八个方向转移,每个方向概率/8，之后在累加

basecase:如果越界，概率为0，没越界，之后k为0，概率为1

vector<pair<int,int>>dir={{-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,vector<vector<vector<double>>>&dp){ //basecase： if(i<0||j<0||i>=n||j>=n){ return 0; } if(k==0){ return 1; } if(dp[i][j][k]!=-1){ return dp[i][j][k]; } double ans=0; for(auto&[dx,dy]:dir){ ans+=f(i+dx,j+dy,k-1,n,dp)/8; } dp[i][j][k]=ans; return ans; }

4.题目四

能够被k整除，我们可以转换为累加和%k==0,我们这里不去设计累加和作为状态，因为累加和个数太多了，而k的范围<=50

状态:f(i,j,k):表示从(i,j)位置出发，累加和%k==r的路径个数有多少个

决策方案:

首先我们选择当前数，并且知道当前需要的余数是r，我们需要算出选择当前数，后续需要的余数是什么?(k+r-(当前数%k))%k

(1)向下转移

(2)向右转移

basecase:

i==n-1&&j==m-1

grid[i][j]%k==r?1:0;

(1)记忆化搜索

//f(i,j,k)：表示从(i,j)出发，整体的累加和%k的结果是r int f(vector<vector<int>>&grid,int k,int i,int j,int r,vector<vector<vector<int>>>&dp){ if(i==grid.size()-1&&j==grid[0].size()-1){ return grid[i][j]%k==r?1:0; } if(dp[i][j][r]!=-1){ return dp[i][j][r]; } //决策方案 int need=(r-(grid[i][j]%k)+k)%k; int ans=0; if(j+1<grid[0].size()) ans=f(grid,k,i,j+1,need,dp); if(i+1<grid.size()) ans=(ans+f(grid,k,i+1,j,need,dp))%mod; dp[i][j][r]=ans; return ans%mod; }