算法知识-从递归入手二维动态规划
一.二维动态规划
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,vector<vector<int>>& grid,vector<vector<int>>& dp){
if(i==0&&j==0){
return grid[0][0];
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int ans=INT_MAX;
if(i-1>=0){
ans=min(ans,f(i-1,j,grid,dp)+grid[i][j]);
}
if(j-1>=0){
ans=min(ans,f(i,j-1,grid,dp)+grid[i][j]);
}
dp[i][j]=ans;
return dp[i][j];
}
int f1(vector<vector<int>>& grid){
int n=grid.size(),m=grid[0].size();
auto dp=vector(n,vector<int>(m,INT_MAX));
dp[0][0]=grid[0][0];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i-1>=0){
dp[i][j]=min(dp[i][j],dp[i-1][j]+grid[i][j]);
}
if(j-1>=0){
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(vector<vector<int>>& grid){
int m=grid[0].size();
int n=grid.size();
vector<int>dp(m,0);
dp[0]=grid[0][0];
//想象的dp表中的第0行的数据
for(int i=1;i<m;i++){
dp[i]=dp[i-1]+grid[0][i];
}
//枚举第1行到第n-1行
for(int i=1;i<n;i++){
//i=1想象中的表的第一行数据
dp[0]+=grid[i][0];
for(int j=1;j<m;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.无法改成动态规划的例题
class Solution {
public:
bool traceback(int row,int col,vector<vector<char>>& board,string &word,int k){
if(k==word.size())return true;
if(word.size()<0||row>=board.size()||row<0||col>=board[0].size()||col<0||board[row][col]!=word[k]){
return false;
}
char tmp=board[row][col];
board[row][col]=0;
bool ans=traceback(row+1,col,board,word,k+1)||
traceback(row-1,col,board,word,k+1)||traceback(row,col-1,board,word,k+1)
||traceback(row,col+1,board,word,k+1);
board[row][col]=tmp;
return ans;
}
bool exist(vector<vector<char>>& board, string word) {
for(int i=0;i<board.size();i++){
for(int j=0;j<board[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],如果两个位置的字符相等，那么他一定是最优的，答案就是这个,
ans=f(len1-1,len2-1)+1
(2)选s[len1-1]，不选t[len2-1],ans=f(len1-1,len2)
(3)不选s[len1-1],选t[len2-1],ans=f(len1,len2-1)
(4)两者都不选一定是最差的解，一定不如(2)(3)所以不用考虑
1.记忆化搜索
int f(int len1,int len2,string &s1,string &s2,vector<vector<int>>&dp){
if(len1==0||len2==0){
return 0;
}
if(dp[len1][len2]!=-1){
return dp[len1][len2];
}
int ans=0;
//如果能两个都选
if(s1[len1-1]==s2[len2-1]){
ans=f(len1-1,len2-1,s1,s2,dp)+1;
}else{
ans=max(f(len1-1,len2,s1,s2,dp),f(len1,len2-1,s1,s2,dp));
}
dp[len1][len2]=ans;
return ans;
}2.严格位置依赖的动态规划
我们画图分析，发现每个格子依赖它的左，它的上和它的左上，所以，我们for循环的大方向是从上到下，从左向右，这样就可以保证，来到某个格子它的左，上，左上，已经被求过了。对于初始值，当len1=0时，那么s1是空串，最长公共子序列为0，当len2=0，那么s2是空串，最长公共子序列为0，所以dp表中的第0行和第0列的初始值为0
int f2(string &s1,string &s2){
int n=s1.size(),m=s2.size();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int j=0;j<=m;j++){
dp[0][j]=0;
}
for(int len1=1;len1<=n;len1++){
dp[len1][0]=0;
for(int len2=1;len2<=m;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(string&s1,string &s2){
//s1作为大的字符串,我们让长度较小的作为列，这样可以节省空间
if(s1.size()<s2.size()){
swap(s1,s2);
}
int n=s1.size(),m=s2.size();
vector<int>dp(m+1,0);
int leftUp=0;
for(int len1=1;len1<=n;len1++){
leftUp=0;
for(int len2=1;len2<=m;len2++){
int tmp=dp[len2];
if(s1[len1-1]==s2[len2-1]){
dp[len2]=leftUp+1;
}else{
dp[len2]=max(dp[len2],dp[len2-1]);
}
leftUp=tmp;
}
}
return dp[m];
}首先我们可以把一个二维数组，压缩成一维数组，所以我们选择字符串长度小的作为列，这样可以让一维数组的大小更小，之后在更新过程中，dp[len2-1]已经被更新了，所以是len1行的dp[len2-1],也就是它的左，之后，当前的dp[len2]还没更新，所以他是len1-1行的dp[len2]，也就是它的上，但是它的左上，数组中无法保存，我们可以使用一个变量leftUp来更新
2.516. 最长回文子序列 - 力扣（LeetCode）
方法一:一个串的最长回文子序列，就是它和它的反转串的最长公共子序列
//方法一:最长回文子序列，就是原串和它的反转串的最长公共子序列
int f3(string&s1,string &s2){
//s1作为大的字符串,我们让长度较小的作为列，这样可以节省空间
if(s1.size()<s2.size()){
swap(s1,s2);
}
int n=s1.size(),m=s2.size();
vector<int>dp(m+1,0);
int leftUp=0;
for(int len1=1;len1<=n;len1++){
leftUp=0;
for(int len2=1;len2<=m;len2++){
int tmp=dp[len2];
if(s1[len1-1]==s2[len2-1]){
dp[len2]=leftUp+1;
}else{
dp[len2]=max(dp[len2],dp[len2-1]);
}
leftUp=tmp;
}
}
return dp[m];
}
int longestPalindromeSubseq(string s) {
string s1=s;
reverse(s.begin(),s.end());
return f3(s,s1);
}方法二:重新设计状态
状态:f(i,j)表示，s字符串的[0,...i]与[j,...n-1]的最长回文子序列有多长
basecase:(1)i==j,ans=1
(2)j==i+1,如果s[i]==s[j],那么ans=1，否则，ans=0(由于我们状态转移，会移动两个单位，所以需要这个basecase)
决策方案:
(1)选s[i]和s[j],前提是s[i]==s[j],那么一定是最优秀的解ans=f(i+1,j-1)+1
(2)选s[i],不选s[j],ans=f(i+1,j)
(3)不选s[i],选s[j],ans=f(i,j+1)
(4)都不选，一定没有(2),(3)优秀
1.记忆化搜索
int f(int i,int j,string&s,vector<vector<int>>&dp){
if(i==j)return 1;
if(j==i+1){
return s[i]==s[j]?2:1;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int ans=0;
//决策方案
if(s[i]==s[j]){
ans=f(i+1,j-1,s,dp)+2;
}else{
ans=max(f(i+1,j,s,dp),f(i,j-1,s,dp));
}
dp[i][j]=ans;
return ans;
}2.严格位置依赖的动态规划
通过画图发现，所有l>r的位置都是非法的格子,之后一个格子需要它的左，它的下，和它的左下，所以我们遍历的大方向是从下到上，从左到右，之后对于l==r为位置，最长回文子序列为1，如果r==l+1,那么判断s[l]==s[r]，如果相等，那么最长回文子序列为2，否则为1
//严格位置依赖的动态规划
int f1(string &s){
int n=s.size();
vector<vector<int>>dp(n,vector<int>(n,1));
for(int i=n-2;i>=0;i--){
dp[i][i+1]=s[i]==s[i+1]?2:1;
for(int j=i+2;j<n;j++){
if(s[i]==s[j]){
dp[i][j]=dp[i+1][j-1]+2;
}else{
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][n-1];
}3.空间压缩
和之前的题目一样，就是它的左，是dp[j-1]，已经转移完了，是当前行的dp[j-1],它的下，是dp[j],是还没转移完的，是i+1行的dp[j],是它的下，之后它的左下，没法保存，所以需要一个变量保存
//状态压缩
int f2(string &s){
int n=s.size();
vector<int>dp(n,1);
int leftDown=1;
for(int i=n-2;i>=0;i--){
leftDown=1;
dp[i+1]=s[i]==s[i+1]?2:1;
for(int j=i+2;j<n;j++){
int tmp=dp[j];
if(s[i]==s[j]){
dp[j]=leftDown+2;
}else{
dp[j]=max(dp[j],dp[j-1]);
}
leftDown=tmp;
}
}
return dp[n-1];
}3.矩阵中的最长递增路径
4.115. 不同的子序列 - 力扣（LeetCode）
我们首先先明确状态，用两个参数i，j(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,vector<vector<int>>&dp){
if(j==0){
return 1;
}
if(i==0){
return 0;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int ans=f(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 n=s.size(),m=t.size();
auto dp=vector(n+1,vector<unsigned>(m+1,0));
for(int i=0;i<=n;i++){
dp[i][0]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;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 n=s.size(),m=t.size();
vector<unsigned>dp(m+1,0);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
if(s[i-1]==t[j-1]){
dp[j]+=dp[j-1];
}
}
}
return dp[m];
}对于空间压缩，每一个格子取决于它的上一个格子和它的左上角的格子，我们从上往下遍历，那么得到上一行的dp表中的格子，之后从右往左遍历，那么左上角就会被保留下来，实现自我更新
5.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
之后最有代价取最小
basecase：
i==0说明源字符串长度为0，要是想要变成长度为j的目标字符串，需要添加j个字符，添加代价为a
a*j
j==0，说明目标字符串长度为0，要是想要变成目标字符串，需要删除i个字符，删除代价为b，b*i
1.记忆化搜索
int f(int i,int j,string &s,string &t,int a,int b,int c,vector<vector<int>>&dp){
if(i==0){
return a*j;
}
if(j==0){
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 ans=f(i-1,j-1,s,t,a,b,c,dp);
if(s[i-1]!=t[j-1]){
//不等需要加上替换
ans+=c;
}
//b:s[0...i-1]对应t[0...j-2]
ans=min(ans,f(i,j-1,s,t,a,b,c,dp)+a);
//s[i-1]不参与
//s[0...i-2]对应t[0...j-1]
ans=min(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 n=s.size(),m=t.size();
auto dp=vector(n+1,vector<int>(m+1,0));
for(int j=0;j<=m;j++){
dp[0][j]=a*j;
}
for(int i=0;i<=n;i++){
dp[i][0]=b*i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;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 n=s.size(),m=t.size();
vector<int>dp(m+1,0);
for(int j=0;j<=m;j++){
dp[j]=a*j;
}
int leftup=0,back=0;
for(int i=1;i<=n;i++){
dp[0]=b*i;
leftup=(i-1)*b;
for(int j=1;j<=m;j++){
back=dp[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],back+b);
leftup=back;
}
}
return dp[m];
}我们发现每个位置依赖左，依赖上，依赖左上。我们从上往下遍历，从左往右遍历，记录leftup
6.97. 交错字符串
状态:f(i,j)表示，当前到s1的前缀长度为i的位置，到s2的前缀长度为j的位置，判断是否存在这个方案(我们只要知道s1的前缀长度，s2的前缀长度我们就能知道当前匹配到s3的前缀长度)。
决策方案:
(1)选s1
判断s1[i]==s3[i+j-1],如果相等，就看s1的前缀长度为i-1,s2的前缀长度为j是否存在(f(i-1,j))，如果都满足ans=true
(2)选s2
判断s2[j]==s3[i+j-1],如果相等，就看s1的前缀长度为i,s2的前缀长度为j-1是否存在(f(i,j-1))，如果都满足
ans=true()()
(3)s1与s2都不选
ans=false
1.记忆化搜索
class Solution {
public:
//表示到达了s1的i长度，到达了s2的j长度当前方案是否存在
bool f(int i,int j,string &s1,string &s2,string &s3,vector<vector<int>>&dp){
if(dp[i][j]!=-1){
return dp[i][j];
}
//basecase:
if(i==0&&j==0){
return true;
}
if(i==0){
return f(0,j-1,s1,s2,s3,dp)&&s3[j-1]==s2[j-1];
}
if(j==0){
return s3[i-1]==s1[i-1]&&f(i-1,0,s1,s2,s3,dp);
}
//决策方案:(1)选s1(2)选s2(3)都不选
bool ans=false;
if(s1[i-1]==s3[i+j-1]){
if(f(i-1,j,s1,s2,s3,dp)){
ans=true;
}
}
if(s2[j-1]==s3[i+j-1]){
if(f(i,j-1,s1,s2,s3,dp))ans=true;
}
dp[i][j]=ans;
return ans;
}
bool isInterleave(string s1, string s2, string s3) {
if(s1.size()+s2.size()!=s3.size())return false;
int n=s1.size(),m=s2.size();
vector<vector<int>>dp(n+1,vector<int>(m+1,-1));
return f(n,m,s1,s2,s3,dp);
}
};2.严格位置依赖的动态规划
我们通过画图分析，发现每个位置依赖它的左和它的上，所以我们从左往右枚举，从上往下枚举
int f2(string &s1,string &s2,string &s3){
int n=s1.size(),m=s2.size();
vector<vector<bool>>dp(n+1,vector<bool>(m+1,false));
dp[0][0]=true;
for(int j=1;j<=m;j++){
if(s2[j-1]!=s3[j-1])break;
dp[0][j]=true;
}
for(int i=1;i<=n;i++){
if(s1[i-1]!=s3[i-1])break;
dp[i][0]=true;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i-1]==s3[i+j-1]){
if(dp[i-1][j]){
dp[i][j]=true;
}
}
if(s2[j-1]==s3[i+j-1]){
if(dp[i][j-1])dp[i][j]=true;
}
}
}
return dp[n][m];
}更多推荐
8
0- 0
已为社区贡献1条内容
所有评论(0)