前言

当递归函数有两个可变参数时，改成的动态规划就是二维的。

一、从递归到二维动态规划

1.最小路径和

class Solution {
public:

    vector<int>move={0,1,0};

    static bool cmp(vector<int>&a,vector<int>&b)
    {
        return a[2]>b[2];
    }

    int minPathSum(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        //return dijkstra(n,m,grid);
        //return recursion(0,0,n,m,grid);
        //vector<vector<int>>dp(n,vector<int>(m,-1));
        //return memorized_search(0,0,n,m,grid,dp);
        //return dynamic_programming(n,m,grid);
        return optimized_dp(n,m,grid);
    }

    int dijkstra(int n,int m,vector<vector<int>>&grid)
    {
        vector<vector<int>>distance(n,vector<int>(m,INT_MAX));
        distance[0][0]=grid[0][0];
        vector<vector<bool>>visited(n,vector<bool>(m,false));
        priority_queue<vector<int>,vector<vector<int>>,decltype(&cmp)>heap(cmp);
        heap.push({0,0,grid[0][0]});

        while(!heap.empty())
        {
            int x=heap.top()[0];
            int y=heap.top()[1];
            heap.pop();

            if(!visited[x][y])
            {
                if(x==n-1&&y==m-1)
                {
                    return distance[x][y];
                }

                visited[x][y]=true;

                for(int i=0;i<2;i++)
                {
                    int nx=x+move[i];
                    int ny=y+move[i+1];
                    
                    if(nx>=0&&nx<n&&ny>=0&&ny<m&&!visited[nx][ny])
                    {
                        if(grid[nx][ny]+distance[x][y]<distance[nx][ny])
                        {
                            distance[nx][ny]=grid[nx][ny]+distance[x][y];
                            heap.push({nx,ny,distance[nx][ny]});
                        }
                    }
                }
            }
        }

        return -1;
    }

    //递归 -> 超时
    int recursion(int x,int y,int n,int m,vector<vector<int>>&grid)
    {
        if(x==n-1&&y==m-1)
        {
            return grid[x][y];
        }
        if(x<0||x>n-1||y<0||y>m-1)
        {
            return INT_MAX;
        }

        int ans=grid[x][y]+min(recursion(x,y+1,n,m,grid),recursion(x+1,y,n,m,grid));

        return ans;
    }

    //记忆化搜索 -> 超时
    int memorized_search(int x,int y,int n,int m,vector<vector<int>>&grid,vector<vector<int>>&dp)
    {
        if(x==n-1&&y==m-1)
        {
            return grid[x][y];
        }
        if(x<0||x>n-1||y<0||y>m-1)
        {
            return INT_MAX;
        }

        if(dp[x][y]!=-1)
        {
            return dp[x][y];
        }

        int ans=grid[x][y]+min(recursion(x,y+1,n,m,grid),recursion(x+1,y,n,m,grid));
        dp[x][y]=ans;
        return ans;
    }

    //动态规划
    int dynamic_programming(int n,int m,vector<vector<int>>&grid)
    {
        vector<vector<int>>dp(n,vector<int>(m));
        dp[n-1][m-1]=grid[n-1][m-1];

        for(int i=n-1;i>=0;i--)
        {
            for(int j=m-1;j>=0;j--)
            {
                if(i==n-1&&j==m-1)
                {
                    continue;
                }
                dp[i][j]=grid[i][j]+min(i+1<=n-1?dp[i+1][j]:INT_MAX,j+1<=m-1?dp[i][j+1]:INT_MAX);
            }
        }

        return dp[0][0];
    }

    //空间压缩
    int optimized_dp(int n,int m,vector<vector<int>>&grid)
    {
        vector<int>dp(m);
        //初始化
        dp[m-1]=grid[n-1][m-1];
        for(int j=m-2;j>=0;j--)
        {
            dp[j]=dp[j+1]+grid[n-1][j];
        }

        for(int i=n-2;i>=0;i--)
        {
            dp[m-1]=grid[i][m-1]+dp[m-1];
            for(int j=m-2;j>=0;j--)
            {
                dp[j]=grid[i][j]+min(dp[j],dp[j+1]);
            }
        }

        return dp[0];
    }
};

其实这个题用dijkstra也能做。（）

观察可知，递归函数肯定有两个可变参数，一个是x坐标一个是y坐标。那么之后就是到了终点就返回终点格子的大小，否则就是当前格子的大小加上下边和右边的最小值。又因为要比较最小值，所以当越界的时候要返回无穷大。

之后记忆化搜索就是挂个dp表即可。

再就是改动态规划，在二维动态规划中，由于有两个可变参数，所以dp表呈现的形式是一个二维网格。之后分析严格位置依赖可知，每个格子依赖自己右方和下方的格子，那么在填格子的时候就从下往上，从右往左填。

然后因为只依赖自己下方和右方的格子，那么就可以只用一个一维数组，只表示当前一行。之后从下往上滚动更新即可。

2.单词搜索

这个题想说明的就是带路径的递归不适合改动态规划。

class Solution {
public:

    vector<int>move={-1,0,1,0,-1};

    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(recursion(i,j,0,word,board))
                {
                    return true;
                }
            }
        }
        return false;
    }

    bool recursion(int x,int y,int i,string &word,vector<vector<char>>&board)
    {
        if(i==word.length())
        {
            return true;
        }
        if(x<0||x>=board.size()||y<0||y>=board[0].size()||board[x][y]!=word[i])
        {
            return false;
        }

        char tmp=board[x][y];//带路径！！！
        board[x][y]=0;
        bool ans=false;
        for(int j=0;j<4;j++)
        {
            ans|=recursion(x+move[j],y+move[j+1],i+1,word,board);
        }
        board[x][y]=tmp;//还原现场
        return ans;
    }
};

因为要求不能走回头路，那么每来到一个格子，都要先把当前格子改成0，之后在回来的时候再还原。那么由此可知，每次递归的时候，可变参数不只两个坐标，还有整个棋盘格，所以没法改成动态规划。

那么整体思路就是遍历棋盘格，即讨论以每个点开头的情况，找到就返回。然后递归函数的可变参数就是两个坐标和当前到的字符串的位置。之后若把字符串遍历到头了就说明找到了，返回true，越界或格子字符对不上就返回false。之后考虑上下左右四个位置，有一个可以就是true，那么就是把四个位置的情况都或起来即可。

3.最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.length();
        int m=text2.length();
        //return recursion(n-1,m-1,text1,text2);
        //return optimized_recursion(n,m,text1,text2);
        //vector<vector<int>>dp(n+1,vector<int>(m+1,-1));
        //return memorized_search(n,m,text1,text2,dp);
        //return dynamic_programming(n,m,text1,text2);
        return optimized_dp(n,m,text1,text2);
    }

    //递归 -> 超时
    int recursion(int i1,int i2,string &text1,string &text2)
    {
        //以结尾讨论可能性 -> 返回text1[0...i1]和text2[0...i2]最长公共子序列长度
        if(i1<0||i2<0)
        {
            return 0;
        }
        int p1=recursion(i1-1,i2-1,text1,text2);//都不要
        int p2=recursion(i1-1,i2,text1,text2);//不要i1位置
        int p3=recursion(i1,i2-1,text1,text2);//不要i2位置
        int p4=text1[i1]==text2[i2]?(p1+1):0;//当前位置一样，都要，去之后讨论，同都不要

        return max(max(p1,p2),max(p3,p4));
    }

    //优化递归 -> 超时
    int optimized_recursion(int len1,int len2,string &text1,string &text2)
    {
        //优化：以长度讨论可能性 -> len1=6 =>text1[0...5] -> 避免边界讨论
        if(len1==0||len2==0)//不可能小于0
        {
            return 0;
        }

        //优化：单调性 -> f(len1-1,len2-1)<=f(len1-1,len2)或f(len1,len2-1)
        int ans;
        if(text1[len1-1]==text2[len2-1])//优化：贪心 -> 字符相等就要，直接结算
        {
            ans=optimized_recursion(len1-1,len2-1,text1,text2)+1;
        }
        else
        {
            ans=max(optimized_recursion(len1-1,len2,text1,text2),
            optimized_recursion(len1,len2-1,text1,text2));
        }

        return ans;
    }

    //记忆化搜索
    int memorized_search(int len1,int len2,string &text1,string &text2,vector<vector<int>>&dp)
    {
        if(len1==0||len2==0)
        {
            return 0;
        }
        if(dp[len1][len2]!=-1)
        {
            return dp[len1][len2];
        }

        int ans;
        if(text1[len1-1]==text2[len2-1])
        {
            ans=memorized_search(len1-1,len2-1,text1,text2,dp)+1;
        }
        else
        {
            ans=max(memorized_search(len1-1,len2,text1,text2,dp),
            memorized_search(len1,len2-1,text1,text2,dp));
        }
        dp[len1][len2]=ans;
        return ans;
    }

    //动态规划
    int dynamic_programming(int n,int m,string &text1,string &text2)
    {
        vector<vector<int>>dp(n+1,vector<int>(m+1,0));

        //初始化 -> 可省略
        // for(int i=0;i<n;i++)
        // {
        //     dp[i][0]=0;
        // }
        // for(int j=0;j<m;j++)
        // {
        //     dp[0][j]=0;
        // }

        //严格位置依赖
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        return dp[n][m];
    }

    //空间压缩
    int optimized_dp(int n,int m,string &text1,string &text2)
    {
        //让较短的作列 -> 省空间
        int row,col;
        if(n>=m)
        {
            row=n;
            col=m;
        }
        else
        {
            row=m;
            col=n;
            string tmp=text1;
            text1=text2;
            text2=tmp;
        }

        vector<int>dp(col+1,0);

        for(int i=1;i<=row;i++)
        {
            int leftUp=0,backUp;
            for(int j=1;j<=col;j++)
            {
                backUp=dp[j];//备份当前格 -> 记录下一格的左上
                if(text1[i-1]==text2[j-1])
                {
                    dp[j]=leftUp+1;
                }
                else
                {
                    dp[j]=max(dp[j],dp[j-1]);
                }
                leftUp=backUp;
            }
        }

        return dp[col];
    }
};

对于子序列问题，还是从结尾位置考虑。

那么递归尝试就是越界了就返回0，否则考虑四种情况，第一种为两个位置都不要，第二三种分别是只要其中一个，第四种就是若当前字符一样就都要，那么结果就是都不要的情况加一长度，最后返回四种情况的最大值即可。

再分析一下可以发现，还可以优化成从长度考虑，这样可以避免边界的讨论。再进一步观察，可以发现题目具有单调性，即两个都不要的情况得出的子序列长度，一定小于等于要其中一个的情况，那么就可以不讨论都不要的情况。之后，再利用贪心优化一下，就是为了让结果尽可能长，那么当两个位置字符一样时就要，然后直接结算。否则再讨论只要一个的情况。

记忆化搜索和严格位置依赖的动态规划直接照着改就行。

对于空间压缩方法，为了进一步节省空间，可以考虑让较短的字符串作dp表长度。再注意记一下左上位置即可。

4.最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.length();
        //return recursion(0,n-1,s);
        //vector<vector<int>>dp(n,vector<int>(n,-1));
        //return memorized_search(0,n-1,s,dp);
        //return dynamic_programming(n,s);
        return optimized_dp(n,s);
    }

    //递归 -> 超时
    int recursion(int l,int r,string &s)
    {
        if(l==r)
        {
            return 1;
        }
        if(l+1==r)
        {
            return s[l]==s[r]?2:1;//单独一个长度为1
        }
        if(s[l]==s[r])
        {
            return 2+recursion(l+1,r-1,s);
        }
        else
        {
            return max(recursion(l+1,r,s),recursion(l,r-1,s));
        }
    }

    //记忆化搜索
    int memorized_search(int l,int r,string &s,vector<vector<int>>&dp)
    {
        if(l==r)
        {
            return 1;
        }
        if(l+1==r)
        {
            return s[l]==s[r]?2:1;
        }

        if(dp[l][r]!=-1)
        {
            return dp[l][r];
        }

        int ans;
        if(s[l]==s[r])
        {
            ans=2+memorized_search(l+1,r-1,s,dp);
        }
        else
        {
            ans=max(memorized_search(l+1,r,s,dp),memorized_search(l,r-1,s,dp));
        }
        dp[l][r]=ans;
        return ans;
    }

    //动态规划
    int dynamic_programming(int n,string &s)
    {
        vector<vector<int>>dp(n,vector<int>(n));
        
        //初始化
        dp[n-1][n-1]=1;
        for(int i=0;i<n-1;i++)
        {
            dp[i][i]=1;
            dp[i][i+1]=s[i]==s[i+1]?2:1;
        }

        for(int i=n-2;i>=0;i--)
        {
            for(int j=i+2;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    dp[i][j]=2+dp[i+1][j-1];
                }
                else
                {
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

        return dp[0][n-1];
    }

    //空间压缩
    int optimized_dp(int n,string &s)
    {
        vector<int>dp(n);
                
        //初始化
        dp[n-1]=1;

        for(int i=n-2;i>=0;i--)
        {
            dp[i+1]=s[i]==s[i+1]?2:1;
            int leftDown=1,backDown;        
            for(int j=i+2;j<n;j++)
            {
                backDown=dp[j];
                if(s[i]==s[j])
                {
                    dp[j]=2+leftDown;
                }
                else
                {
                    dp[j]=max(dp[j],dp[j-1]);
                }
                leftDown=backDown;
            }
        }

        return dp[n-1];

    }
};

这个可以说是区间dp的初见了，因为是要求回文子序列，所以整体思路就是从头尾往中间考虑。

递归尝试就是当相遇了就返回1，若最后剩两个，那么若这两个相等，就构成了一个回文，返回2；否则就只算自己返回1。之后若当前两位置一样就是2+去中间递归的结果，否则就是两个只要一个的最大值。

之后是严格位置依赖的动态规划，画出dp表，首先观察尝试函数中的basecase，可以发现，只有j大于等于i的格子才有效，即上三角区域。然后可以发现对角线上的值都为1，右侧的格子取决于是否相等。之后分析严格位置依赖，可以发现每个格子依赖左侧，下方和左下的格子，那么填的顺序就是从下往上从左往右。

空间压缩就是注意存一下左下的格子即可。

5.二叉树

#include<bits/stdc++.h>
using namespace std;

const int MOD=1000000007;
typedef long long ll;

//递归 -> 超时
int recursion(int n,int m)
{
    if(n==0)//空树
    {
        return 1;
    }
    if(m==0)
    {
        return 0;
    }

    int ans=0;
    for(int i=0;i<n;i++)
    {
        ans=(ans+(recursion(i, m-1)*recursion(n-i-1, m-1))%MOD)%MOD;
    }

    return ans;
}
//记忆化搜索
int memorized_search(int n,int m,vector<vector<int>>&dp)
{
    if(n==0)
    {
        return 1;
    }
    if(m==0)
    {
        return 0;
    }
    if(dp[n][m]!=-1)
    {
        return (int)dp[n][m];
    }

    int ans=0;
    for(int i=0;i<n;i++)
    {
        ans=(ans+((ll)memorized_search(i, m-1,dp)*memorized_search(n-i-1, m-1,dp))%MOD)%MOD;
    }
    dp[n][m]=ans;
    return ans;
}

//动态规划
int dynamic_programming(int n,int m)
{
    vector<vector<int>>dp(n+1,vector<int>(m+1));
    
    //初始化
    for(int j=0;j<m;j++)
    {
        dp[0][j]=1;
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<i;k++)
            {
                dp[i][j]=(dp[i][j]+((ll)dp[k][j-1]*dp[i-k-1][j-1])%MOD)%MOD;
            }
        }
    }

    return dp[n][m];
}

//空间压缩
int optimized_dp(int n,int m)
{
    vector<int>dp(n+1);

    dp[0]=1;

    for(int j=1;j<=m;j++)//先枚举列！！
    {
        for(int i=n;i>=1;i--)//从下往上
        {
            dp[i]=0;//不依赖左侧格子 -> 重置！！！
            for(int k=0;k<i;k++)
            {
                dp[i]=(dp[i]+((ll)dp[k]*dp[i-k-1]))%MOD;
            }
        }
    }

    return dp[n];
}

int solve(int n,int m)
{
    //return recursion(n,m);
    //vector<vector<int>>dp(n+1,vector<int>(m+1,-1));
    //return memorized_search(n,m,dp);
    //return dynamic_programming(n,m);
    return optimized_dp(n,m);
}

void read()
{
    int n,m;
    cin>>n>>m;
    cout<<solve(n,m);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    return 0;
}

这个题就是计算种类数的公式需要点思考。

公式就是，比如当还剩5个节点时，当前节点的两个孩子可以是0个和5个，1个和4个……5个和0个，那么总的种类数就是每个种类相乘后相加。注意，当n＝0时是空树，也算一种。

之后递归尝试每次遍历当前所有情况即可。

严格位置依赖的动态规划只需要注意n＝0的那一行全是1即可。

重点是空间压缩，由于每个格子依赖自己左上到自己那一行的某些格子，所以考虑将压缩的数组看作竖着的列，那么此时滚动时就要先从左往右，再从下往上，即要先枚举列。其中还要注意由于不依赖自己左侧的格子，那么每次自己左侧的格子要重置。

 6.矩阵中的最长递增路径

class Solution {
public:

    vector<int>move={-1,0,1,0,-1};

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int n=matrix.size();
        int m=matrix[0].size();

        int ans=0;
        vector<vector<int>>dp(n,vector<int>(m));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                //ans=max(ans,recursion(i,j,n,m,matrix));
                ans=max(ans,memorized_search(i,j,n,m,matrix,dp));
            }
        }

        return ans;
    }

    //递归 -> 超时
    int recursion(int x,int y,int n,int m,vector<vector<int>>&matrix)
    {
        int next=0;
        if(x-1>=0&&matrix[x][y]<matrix[x-1][y])
        {
            next=max(next,recursion(x-1,y,n,m,matrix));
        }
        if(x+1<n&&matrix[x][y]<matrix[x+1][y])
        {
            next=max(next,recursion(x+1,y,n,m,matrix));
        }
        if(y-1>=0&&matrix[x][y]<matrix[x][y-1])
        {
            next=max(next,recursion(x,y-1,n,m,matrix));
        }
        if(y+1<m&&matrix[x][y]<matrix[x][y+1])
        {
            next=max(next,recursion(x,y+1,n,m,matrix));
        }

        return next+1;
    }

    //记忆化搜索
    int memorized_search(int x,int y,int n,int m,vector<vector<int>>&matrix,
    vector<vector<int>>&dp)
    {
        if(dp[x][y]!=0)
        {
            return dp[x][y];
        }

        dp[x][y]=1;
        for(int i=0,nx,ny;i<4;i++)
        {
            nx=x+move[i];
            ny=y+move[i+1];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&matrix[x][y]<matrix[nx][ny])
            {
                dp[x][y]=max(dp[x][y],memorized_search(nx,ny,n,m,matrix,dp)+1);
            }
        }

        return dp[x][y];
    }
};

这个题也属于没法改成动态规划的，原因就是每个格子都依赖自己上下左右四个方向，没有严格位置依赖。

那么思路就是以每个点为起点去跑递归。每次都去四个方向比自己大的格子递归即可。

二、更多二维动态规划题目

1.不同的子序列

class Solution {
public:

    int MOD=1000000007;

    int numDistinct(string s, string t) {
        //return DP(s,t);
        return optimized_dp(s,t);
    }

    //动态规划
    int DP(string &s,string &t)
    {
        int n=s.length();
        int m=t.length();
        vector<vector<int>>dp(n+1,vector<int>(m+1));

        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][j]+dp[i-1][j-1])%MOD;
                }
            }
        }

        return dp[n][m];
    }

    //空间压缩
    int optimized_dp(string &s,string &t)
    {
        int n=s.length();
        int m=t.length();

        vector<int>dp(m+1);
        
        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]+dp[j-1])%MOD;
                }
            }
        }

        return dp[m];
    }
};

这个题的分析就比较简单了，还是考虑结尾，就是不要当前位置和如果相等就要当前位置这两种情况相加。

那么basecase就是当目标字符串是空串时，就只有一种情况，即子序列是空串。

空间压缩时，需要注意，由于每个格子依赖左侧未更新的值，所以要从右往左更新！！！

2.编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.length();
        int m=word2.length();
        //return DP(n,m,word1,word2);
        return optimized_dp(n,m,word1,word2);
    }

    //动态规划
    int DP(int n,int m,string &word1,string &word2)
    {
        vector<vector<int>>dp(n+1,vector<int>(m+1));

        for(int i=1;i<=n;i++)
        {
            dp[i][0]=i;
        }
        for(int j=1;j<=m;j++)
        {
            dp[0][j]=j;
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int p1=word1[i-1]==word2[j-1]?dp[i-1][j-1]:INT_MAX;//直接用
                int p2=word1[i-1]!=word2[j-1]?dp[i-1][j-1]+1:INT_MAX;//替换
                int p3=dp[i][j-1]+1;//插入
                int p4=dp[i-1][j]+1;//删除
                dp[i][j]=min(min(p1,p2),min(p3,p4));
            }
        }

        return dp[n][m];
    }

    //空间压缩
    int optimized_dp(int n,int m,string &word1,string &word2)
    {
        vector<int>dp(m+1);

        for(int j=0;j<=m;j++)
        {
            dp[j]=j;
        }

        for(int i=1;i<=n;i++)
        {
            int leftUp=i-1,backUp;
            dp[0]=i;//注意dp[0]和leftUp的初始化！！
            for(int j=1;j<=m;j++)
            {
                backUp=dp[j];
                int p1=word1[i-1]==word2[j-1]?leftUp:INT_MAX;
                int p2=word1[i-1]!=word2[j-1]?leftUp+1:INT_MAX;
                int p3=dp[j-1]+1;
                int p4=dp[j]+1;
                dp[j]=min(min(p1,p2),min(p3,p4));
                leftUp=backUp;
            }
        }

        return dp[m];
    }
};

这个题还是从结尾考虑，然后去讨论不同情况的位置依赖。那么就是当让当前字符参与的话，若想让当前字符变成目标字符，如果和目标字符一样，那就可以直接用，不消耗代价；若不一样，那就可以考虑替换，代价加一；若不让当前字符变成目标字符，那么就是插入一个字符；还有，若不让当前字符参与，直接删除即可。最后这四种情况取最小值即可。那么basecase就是若目标串为空串，那么当前串的所有字符都要删除；若当前串是空串，那么就要全插入。

空间压缩时要注意的就是dp[0]和leftUp的初始化。

3.交错字符串

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n=s1.length();
        int m=s2.length();

        if(n+m!=s3.length())
        {
            return false;
        }

        //return DP(n,m,s1,s2,s3);
        return optimized_dp(n,m,s1,s2,s3);
    }

    //动态规划
    bool DP(int n,int m,string &s1,string &s2,string &s3)
    {
        vector<vector<bool>>dp(n+1,vector<bool>(m+1));

        dp[0][0]=true;
        for(int i=1;i<=n;i++)
        {
            if(s1[i-1]!=s3[i-1])
            {
                break;
            }
            dp[i][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++)
        {
            for(int j=1;j<=m;j++)
            {
                bool p1=s1[i-1]==s3[i+j-1]&&dp[i-1][j];
                bool p2=s2[j-1]==s3[i+j-1]&&dp[i][j-1];

                dp[i][j]=p1||p2;
            }
        }

        return dp[n][m];
    }

    //空间压缩
    bool optimized_dp(int n,int m,string &s1,string &s2,string &s3)
    {
        vector<bool>dp(m+1);

        dp[0]=true;
        for(int j=1;j<=m;j++)
        {
            if(s2[j-1]!=s3[j-1])
            {
                break;
            }
            dp[j]=true;
        }

        for(int i=1;i<=n;i++)
        {
            dp[0]=s1[i-1]==s3[i-1]&&dp[0];//注意dp[0]的更新！！！
            for(int j=1;j<=m;j++)
            {
                bool p1=s1[i-1]==s3[i+j-1]&&dp[j];
                bool p2=s2[j-1]==s3[i+j-1]&&dp[j-1];

                dp[j]=p1||p2;
            }
        }

        return dp[m];
    }
};

这个题还是考虑结尾，之后再去分析情况。那么情况就是，第一个情况就是让s1当前字符去拼，那么就是若s1的当前字符等于s3的当前字符，且用s1的之前字符能拼出当前s3；另一个情况就是让s2的当前字符去拼，那么就是s2当前字符是否等于且用s2之前字符能拼出来。所以最终结果就是两种可能性或起来。那么basecase就是若s1或s2分别为空时，只要和s3对上了就是true，只要出现不一样之后就都是false。

空间压缩时要注意的就是dp[0]的更新！！

4.有效涂色问题

给定n,m两个参数，一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选。当涂满n个格子，并且m种颜色都使用了，为一种有效方法。求一共有多少种有效方法。

数据范围：1<=n,m<=5000，答案对1000000007取模。

#include<bits/stdc++.h>
using namespace std;

const int MOD=1000000007;
typedef long long ll;

int f(int i,int n,int m,vector<int>&path,vector<bool>&set)
{
	if(i==n)
	{
		fill(set.begin(),set.end(),false);
		int colors=0;
		for(int c:path)
		{
			if(!set[c])
			{
				set[c]=true;
				colors++;
			}
		}
		return colors==m?1:0;
	}
	else
	{
		int ans=0;
		for(int j=1;j<=m;j++)
		{
			path[i]=j;
			ans=(ans+f(i+1,n,m,path,set))%MOD;
		}
		return ans;
	}
}

int ways1(int n,int m)
{
	vector<int>path(n);
	vector<bool>set(m+1);
	return f(0,n,m,path,set);
}

int ways2(int n,int m)
{
	vector<vector<int>>dp(n+1,vector<int>(m+1));
	
	for(int i=1;i<=n;i++)
	{
		dp[i][1]=m;
	}
	
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=m;j++)
		{
			dp[i][j]=((ll)dp[i-1][j]*j)%MOD;
			dp[i][j]=(dp[i][j]+((ll)dp[i-1][j-1]*(m-j+1)%MOD))%MOD;
		}
	}
	
	return dp[n][m];
}

void read()
{
	cout<<"Start testing ans"<<endl;
	int n=9;
	int m=9;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int ans1=ways1(i,j);
			int ans2=ways2(i,j);
			if(ans1!=ans2)
			{
				cout<<"Wrong!"<<endl;
			}
		}
	}
	cout<<"Test ends"<<endl;
	
	cout<<"Start testing time"<<endl;
	n=5000;
	m=4877;
	auto start=chrono::high_resolution_clock::now();
	ways2(n,m);
	auto end=chrono::high_resolution_clock::now();
	chrono::duration<double>elapsed=end-start;
	cout<<"DP costs "<<elapsed.count()<<" seconds"<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	return 0; 
}

高中的排列组合还在追我。（悲）

这个题的情况讨论就比较简单了，就是若前一个格子已经涂了j种颜色，那么这个格子就可以随便涂，情况数就是上一个的情况数乘以j；若上一个格子涂了j-1种，那么当前格子就有m-（j-1）种涂法。总的情况数就是这两个相加。

5.删除至少几个字符可以变成另一种字符串的子串

给定两个字符串s1和s2，返回s1至少删除多少字符可以成为s2的子串。

#include<bits/stdc++.h>
using namespace std;

string randomString(int n,int v)
{
	string ans;
	for(int i=0;i<n;i++)
	{
		ans+='a'+rand()%v;
	}
	return ans;
}

int f(string &s1,int i,string path,vector<string>&list)
{
	if(i==s1.length())
	{
		list.push_back(path);
	}
	else
	{
		f(s1,i+1,path,list);
		path+=s1[i];
		f(s1,i+1,path,list);
	}
}

int ways1(string s1,string s2)
{
	vector<string>list;
	string path;
	f(s1,0,path,list);
	sort(list.begin(),list.end(),
	[&](string &a,string &b){return a.length()>b.length();});
	for(string str:list)
	{
		if(s2.find(str)!=string::npos)
		{
			return s1.length()-str.length(); 
		}
	}
	return s1.length();
}

int ways2(string s1,string s2)
{
	int n=s1.length();
	int m=s2.length();
	
	//dp[i][j] -> s1前i个字符至少删掉几个字符能变成s2前j个字符的任意后缀串 
	vector<vector<int>>dp(n+1,vector<int>(m+1));
	
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=i;
		for(int j=1;j<=m;j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				dp[i][j]=dp[i-1][j-1];
			}
			else
			{
				dp[i][j]=1+dp[i-1][j];
			}
		}
	}
	
	//返回最后一行的最小值
	int ans=INT_MAX; 
	for(int j=0;j<=m;j++)
	{
		ans=min(ans,dp[n][j]);
	}
	
	return ans;
}

void read()
{
	srand(time(0));
	int n=12;
	int v=3;
	int testTime=20000;
	cout<<"Start testing ans"<<endl;
	for(int i=0;i<testTime;i++)
	{
		int len1=rand()%n+1;
		int len2=rand()%n+1;
		string s1=randomString(n,v);
		string s2=randomString(n,v);
		int ans1=ways1(s1,s2);
		int ans2=ways2(s1,s2);
		if(ans1!=ans2)
		{
			cout<<"Wrong"<<endl;
		}
	}
	cout<<"Test ends"<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	return 0; 
}

这个题的思路就属于没有那点灵机一动打死也想不出来的……

最逆天的就是这个对dp表的定义。dp[i][j]在这里定义为s1的前i个字符至少删掉几个能变成s2的前j个字符的任意后缀串，之后答案要取dp表最后一行的最小值……

那么有了这个定义就好分析情况了，就是若两位置相等就不用删，否则就删一次即可。

总结

这么看下来，动态规划的核心就是分析情况。当遇到子序列或者子串问题时，一定要记得优先考虑结尾。在空间压缩时，最保险最直观的方法还是画出dp表，然后对照dp表去考虑压缩时的更新细节。

END

# 动态规划 # 算法 # c++ # leetcode # 深度优先
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR巡检哪家好，和浪潮比哪家方案更成熟

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区
cover

瑞丰宝丽在AR巡检领域排名

avatar 乐奇 Rokid 开放社区