动态规划类题目总结

最后更新时间：2023年09月03日

动态规划类题目总结

动态规划一直是自己的弱项，当时学01背包都学了好久，特别是遇到动态规划题的时候，看得懂答案，但就是不会做。

动态规划的三大步骤：

同台规划的思想：利用历史记录，避免我们重复计算。而这些历史记录需要用一位数组或二维数组保存。
第一步：定义数组元素含义。如：$dp[i]$是什么意思？
第二步：找出数组元素的关系式。类似高中的数学归纳法。
如：
这一步也是最难的一步。
第三步：找出初始值。虽然我们知道了数组元素之间的关系式，例如 $dp[n] = dp[n-1] + dp[n-2]$，但一直推下去的话，会由 $dp[3] = dp[2] + dp[1]$。 $dp[2]$ 和 $dp[1]$ 是不能再分解的了，这就是初始值。

案例：

案例一：简单一维DP

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
  1. 定义数组元素
    定义 $dp[i]$ 的含义为：跳上一个 i 级的台阶总共有 $dp[i]$ 种跳法。

  2. 找出元素间的关系式
    青蛙可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式

    • 一种是从第 n-1 级跳上来
    • 一种是从第 n-2 级跳上来

    由于我们是要算所有可能的跳法的，所以有 $dp[n] = dp[n-1] + dp[n-2]$。

  3. 找出初始条件
    显然，$dp[2] = 2$, $dp[1]=1$,$ dp[0]=0$
    注意，初始化一定要找全，不能把$dp[2]$漏掉！

代码如下：

#include<iostream>
using namespace std;
int main(){
    int dp[105];
    int n;
    cin>>n; 
    dp[0]=1;
    dp[1]=1;
    for(int i = 2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    
    cout<<dp[n]<<endl;
    return 0;
}

案例二：二维数组DP

一个机器人位于一个 $m \times n$ 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？


这是某年蓝桥杯的一个省赛题，也是leetcode第62题。

  1. 定义数组元素
    定义 $dp[i]$ 的含义为：当机器人从左上角走到$(i, j)$ 这个位置时，一共有 $dp[i] [j]$ 种路径。

  2. 找出元素间的关系式
    机器人到达$(i,j)$有两种方式

    • 从$(i-1,j)$ 这个位置走一步到达
    • 从$(i,j-1)$ 这个位置走一步到达

    因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 $dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]$。

  3. 找出初始条件
    $dp[0] [0….n-1] = 1$; 相当于最上面一行，机器人只能一直往右走
    $dp[0…m-1] [0] = 1$; 相当于最左面一列，机器人只能一直往下走

代码如下：

#include<iostream>
using namespace std;
long long dp[10][10];
int main(){
    int m = 3;
    int n = 7;
    
    dp[1][1]=1;
    
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<=n;j++){
            dp[i][1]=1;
            dp[1][j]=1;        
        }
    }
    
    for(int i = 2;i<=m;i++){
        for(int j = 2;j<=n;j++){
            if(i==1){
                dp[i][j]=dp[i][j-1];
            }
            else if(j==1){
                dp[i][j]=dp[i-1][j];
            }
            else{
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<=n;j++){
                cout<<dp[i][j]<<"\t";
            }
        cout<<endl;
        }
}

案例三：二维数组DP

给定一个包含非负整数的 $m \times n$ 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

举例：

输入:
arr = [
          [1,3,1],
          [1,5,1],
          [4,2,1]
      ]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

这是leetcode第64题。

  1. 定义数组元素
    定义 $dp[i]$ 的含义为：当机器人从左上角走到$(i, j)$ 这个位置时，最下的路径和是 $dp[i] [j]$

  2. 找出元素间的关系式
    机器人到达$(i,j)$有两种方式

    • 从$(i-1,j)$ 这个位置走一步到达
    • 从$(i,j-1)$ 这个位置走一步到达

    因为是计算哪一个路径和是最小的，所以要从这两种方式中，选择一种，使得$dp[i] [j] $的值是最小的，显然有：

    dp[i] [j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格种的值
  3. 找出初始条件
    $dp[0] [0….n-1] = 1$; 相当于最上面一行，机器人只能一直往右走
    $dp[0…m-1] [0] = 1$; 相当于最左面一列，机器人只能一直往下走

代码如下：

#include<iostream>
using namespace std;
int main(){
    int grid[201][201];
    long long dp[201][201];
    int m=2;
    int n=3;
    for(int i=1;i<=m;++i){
        for(int j = 1;j<=n;++j){
            cin>>grid[i][j];
        }
    }
    
    dp[1][1]=1;
    for(int i = 2;i<=m;++i){
        dp[i][1]=dp[i-1][1]+grid[i][1];
    }
    for(int j = 2;j<=n;++j){
        dp[1][j]=dp[1][j-1]+grid[1][j];
    }
    for(int i=2;i<=m;++i){
        for(int j = 2;j<=n;++j){
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
    cout<<dp[m][n];
    
}

案例四：编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符、删除一个字符、替换一个字符。

示例：

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

这个题自己自己琢磨了一晚上，在leetcode第72题，是hard级别。

经验：90%的字符串问题都可以用动态规划解决，并且90%是采用二维数组。

  1. 定义数组元素
    定义$ dp[i]$ 的含义为：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为$ dp[i] [j]$。

  2. 找出元素间的关系式
    由于我们是要让操作的次数最小，所以我们要寻找最佳操作。那么有如下关系式：

    • 如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 $dp[i] [j] = dp[i-1] [j-1]$。（别忘了$ dp[i] [j]$ 的含义哈）。
    • 如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：
      （1）如果把字符 word1[i] 替换成与 word2[j] 相等，则有 $dp[i] [j] = dp[i-1] [j-1] + 1$;
      （2）如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有$ dp[i] [j] = dp[i] [j-1] + 1$;
      （3）如果把字符 word1[i] 删除，则有$ dp[i] [j] = dp[i-1] [j] + 1$;

那么我们应该选择一种操作，使得$ dp[i] [j]$ 的值最小，显然有
$dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1$;

  1. 找出初始条件
    显然，当$ dp[i] [j] $中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的$ dp[0] [0….n] $和所有的 $dp[0….m] [0]$。这个还是非常容易计算的，因为当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。

代码如下：

#include<iostream>
#include<cstring>
using namespace std;
char a[505]="";
char b[505]="";
int dp[501][501];


int main(){
    cin>>a;
    cin>>b;
    int m = strlen(a);
    int n = strlen(b);
    for(int i = 0;i<=m;i++){
        dp[i][0]=i;
    }    
    for(int j = 0;j<=n;++j){
        dp[0][j]=j;
    }
    for(int i = 1;i<=m;++i){
        for(int j = 1;j<=n;++j){
            if(a[i-1]==b[j-1]){
                dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]);
            }
            else{
                dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
            }
        }
    }
    
    for(int i = 0;i<=m;++i){
        for(int j = 0;j<=n;++j){
            cout<<dp[i][j]<<"\t";
        }
        cout<<endl;
    }
    
    return 0;
}

加油吧，道阻路长。

声明：奋斗小刘|版权所有，违者必究|如未注明，均为原创|本网站采用BY-NC-SA协议进行授权

转载：转载请注明原文链接 - 动态规划类题目总结

Make Everyday Count