动态规划刷题总结

什么是动态规划？

​ 动态规划的本质是枚举，一般问题形式是求最值，求出所有可能解，在其中找最值解决问题。很多问题都不能直接用动态规划解决，需要稍微转换一下，但核心还是动态规划求最值，需要好好辨析。

动规怎么用？

以0-1背包问题为例：

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

第一步：明确状态和选择

状态就是解决问题需要的变量，选择就是对状态的修改策略

解决0-1背包问题需要两个变量：背包的容量 和 可选择的物品，修改背包容量有两钟策略：将可选的物品装进背包 或 不装进背包 ，所以状态为 背包的容量 w[j] 和 可选择的物品 n[i]，选择为 将可选的物品装进背包 或 不装进背包。

第二步：明确状态转移方程（递推公式）

状态转移方程描述了解决问题的过程，将原问题的解决分解成有次序的若干步，后一步依赖于前一步，状态转移方程描述了如何根据第 i-1 步推出第 i 步， 进而解决整个问题。我们要根据 选择 推出状态转移方程。

如何解决背包问题？背包问题要求 当背包容量为W时，在N个物品中选择，能装下的最大价值，我们要解决当背包容量为j时，在i个物品中选择，能装下的最大价值（j<=W,i<=N)，那么当j=W,i=N时，问题得以解决。那么如何根据前一步的状态 f(i-1,j-1) 推出后一步 f(i,j) ？两种情况：①将可选物品装进背包：f(i,j)= f(i,j-1) +val[i] ②不装进背包 f(i,j)= f(i-1,j-1) , 要求最大价值即 f(i，j) = max{f(i,j-1)，f(i-1,j-1)}。

①确认base case: f(0)

背包问题中，当 i=0 或 j=0 时 f(0,…)=f(…,0)=0

②推出通用状态转移方程: f(i)=g(f(i-1))

根据上文解释，背包问题 f(i，j) = max{f(i,j)= f(i,j-1) +val[i]，f(i-1,j-1)}

第三步：枚举所有状态得到最值

最后，根据 状态转移方程 枚举出所有 状态 下的解，得到最值，解决问题。

第四步：优化

​ 考虑是否有重复解决的子问题，是否需要设置备忘录进行记录；考虑是否只需记录有限个状态但实际记录了所有状态造成空间的浪费，是否可以进行空间压缩。具体解法具体分析。

动规的具体解法

​ 动态规划解题由于第三步：枚举 的方式不同，分成了递归、迭代两种解法。递归自顶向下通过递归方法 f 来描述状态转移方程解决问题，迭代自底向上通过数组 dp 描述状态转移方程，记录所有解，在所有解中找最值，进而解决问题。关键是 f 和 dp 的定义如何确定，上文 明确动态转移方程 已经讲到，f 和 dp描述的就是动态转移方程。递归可以改迭代，迭代可以改递归，它们只是枚举方式不同，其他并无两样。

迭代解法

​ 对于迭代枚举所有解，将其存放在dp数组，当 状态 有多个时，需要dp为多维数组（顶多二维数组）；当dp数组过于复杂不能很好地解决问题时，要重新思考dp的定义；dp数组的最后一个值不一定是问题的最终解，也有可能是dp数组中的最大/小值，看dp数组的定义如何。

解法框架：

//给用来存储的数据结构和dp数组分配空间
//base case

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)
        
 return dp[最终状态1][最终状态2][...] or 选最值(dp)

背包问题迭代解法：

int knapsack(int W, int N, int[] wt, int[] val) {
     //dp[i][w] 表示：对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]
    int[][] dp = new int[N + 1][W + 1];
    
    // base case
    //重量或物品为0时，背包无法存放物品
    for(int i=0;i<N;i++) dp[i][0]=0;
    for(int j=0;j<W;j++) dp[0][j]=0;
    
    for (int i = 1; i <= N; i++) &#123;
        for (int w = 1; w <= W; w++) &#123;
            if (w - wt[i - 1] < 0) &#123;
                // 物品重量超过背包剩余可装重量，不装入背包
                dp[i][w] = dp[i - 1][w];
            &#125; else &#123;
                // 装入或者不装入背包，择优
                dp[i][w] = Math.max(
                    dp[i - 1][w - wt[i-1]] + val[i-1], 
                    dp[i - 1][w]
                );
            &#125;
        &#125;
    &#125;
    
    return dp[N][W];
&#125;

由于数组索引从 0 开始，而我们定义中的 i 是从 1 开始计数的，所以 val[i-1] 和 wt[i-1] 表示第 i 个物品的价值和重量,如果选择将第 i 个物品装进背包，那么第 i 个物品的价值 val[i-1] 肯定就到手了，接下来就要在剩余容量 w - wt[i-1] 的限制下，在前 i - 1 个物品中挑选，求最大价值，即 dp[i-1][w - wt[i-1]]

递归解法

​ 递归比较好理解，它是自上而下的，描述了如何解决问题，只要明确定义，根据定义写逻辑就能得到解，递归方法 f 的返回值就是不同状态下解的值。

解法框架：

//备忘录memo
//递归函数结果res
main(...){
    //初始化备忘录
    return dp() or dp()
}
dp(状态1,状态2,...){
    //base case
    
    //查备忘录，有就return
    res=择优(选择1，选择2...);
    //添加备忘录
    
    //return
}

背包问题递归解法：

//备忘录memo[i][w]:对于前 i 个物品（从 1 开始计数），当前背包的容量为 w 时，这种情况下可以装下的最大价值
int[][] memo;
int knapsack(int W, int N, int[] wt, int[] val) {
    //初始化备忘录
    memo = new int[N + 1][W + 1];
       return dp(W,N,wt,val);
}

//dp(W,N,wt,wal)返回装载重量为 `W` 的背包和 `N` 个物品可装载的最大价值
int res;
int dp(int W,int N,int[] wt,int[] val){
    //base case
    if(N==0||W==0) return 0;
    //查备忘录
    if(memo[N][W]!=0) return memo[N][W];
    //物品重量超过背包剩余可装重量，不装入背包
    if (w - wt[i - 1] < 0)&#123;
        res=dp(W,N-1,wt,val);
    &#125;else&#123;
        //物品装入或者不装入背包，择优
        res=Math.max(res,dp(W-wt[N]+val[N],N-1,wt,val));
    &#125;   
    memo[N][W]=res;
    
    return res;
&#125;

综上，动规解法如下：

1. 根据问题，明确状态和选择
2. 根据选择，明确状态转移方程
   1. 确定base case
   2. 写出通用的状态转移方程
3. 通过状态转移方程，枚举所有状态下的解，求最值
   • 通过递归枚举
   • 通过迭代枚举
4. 时空优化
   • 递归解法设备忘录
   • 迭代解法压缩空间

一个小栗子：最小编辑距离

力扣72题：编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

思路

解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串，然后一步步往后走，缩小问题的规模。

对于每对字符s1[i]和s2[j]，可以有四种操作：

if s1[i] == s2[j]:
       跳过（skip）
    i, j 同时向前移动
else:
    三选一：
        插入（insert）
        删除（delete）
        替换（replace）

迭代解法：

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        //存储 s1[0..i] 和 s2[0..j] 的最小编辑距离
        int[][] dp=new int[m+1][n+1];
        //base case
        for(int i=1;i<=m;i++)&#123;
          dp[i][0]=i;
        &#125;
        for(int j=1;j<=n;j++)&#123;
            dp[0][j]=j;
        &#125;
        //三选一
        for(int i=1;i<m+1;i++)&#123;
            for(int j=1;j<n+1;j++)&#123;
                if(word1.charAt(i-1)==word2.charAt(j-1))
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1);
            &#125;
        &#125;
        return dp[m][n];
    &#125;

    public int min(int a,int b,int c)&#123;
        return Math.min(a,Math.min(b,c));
    &#125;
&#125;

再来一个栗子：最长公共子序列

力扣1143题 计算LCS

输入两个字符串s1和s2，请你找出他们俩的最长公共子序列，返回这个子序列的长度。

思路

对于每对字符s1[i]和s2[j]，可以有四种情况：

1. 如果s1[i]==s2[j],这个字符一定在lcs中
2. 如果s1[i]！=s2[j]，s1[i]和s2[j]至少有一个字符不在lcs中
   1. s1[i]不在lcs中
   2. s2[j]不在lcs中
   3. 都不在lcs中

2中情况3可以直接忽略，因为我们在求最大值，情况三在计算s1[i+1..]和s2[j+1..]的lcs长度，这个长度肯定是小于等于情况二s1[i..]和s2[j+1..]中的lcs长度的，因为s1[i+1..]比s1[i..]短，那从这里面算出的lcs当然也不可能更长，同理，情况三的结果肯定也小于等于情况一。

迭代解法：

int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
    // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
    // base case: dp[0][..] = dp[..][0] = 0

    for (int i = 1; i <= m; i++) &#123;
        for (int j = 1; j <= n; j++) &#123;
            // 现在 i 和 j 从 1 开始，所以要减一
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) &#123;
                // s1[i-1] 和 s2[j-1] 必然在 lcs 中
                dp[i][j] = 1 + dp[i - 1][j - 1];
            &#125; else &#123;
                // s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            &#125;
        &#125;
    &#125;

    return dp[m][n];
&#125;