从零备战蓝桥杯——动态规划（递推篇）

---

双非刷leetcode备战2023年蓝桥杯，qwq加油吧，无论结果如何总会有收获！一起加油,我是跟着英雄哥的那个思维导图刷leetcode的，大家也可以看看所有涉及到的题目用leetcode搜索就可以哦，因为避让添加外链，一起加油！！！

动态规划将分为五个板块来讲，本篇为基础dp篇都是基础题目适合入门

---

---

基础篇：

不会吧不会吧，你连dp的基础都不会，我不信我不信，反正我会(！我也不会，略懂一点点)，这是一种思想吧，如果不会的话可以看我这几篇博文，一个是八皇后的，一个是递推的，我就不添加链接了哈，直接点头像就能看~话不多说你要是看完了咱就直接开始刷题 ，这其实就是一种思想，我认为直接刷题就可以了~所以咱直接刷题哈，因为题目会告诉咱啥叫动态规划~

五步走

• 1. 确定dp数组下标含义
• 2. 递推公式
• 3. 初始化
• 4. 遍历顺序
• 5. 推导结果

当然不是所有的dp问题都这么简单的能找到

---

Leetcode相关题目

基础dp：

各种递推题目

如：509,70,746.各位可以刷刷

二维递推：62. 不同路径

思路：不会的看我的博文:4000字，让你明白递推及其例题做法（C语言，有图）点头像就有哈，里面有个马兰过河卒问题，一模一样的（没障碍这个）

class Solution {
public:
    int uniquePaths(int m, int n) {
    int a[m+1][n+1];
    for(int i=1;i<=m;i++)
    {
        a[i][1]=1;
    }
       for(int i=1;i<=n;i++)
    {
        a[1][i]=1;
    }
    //初始化
    for(int i=2;i<=m;i++)
    {
        for(int j=2;j<=n;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1];
        }
    
    }
    return a[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二维递推：63. 不同路径

思路：不会的看我的博文:4000字，让你明白递推及其例题做法（C语言，有图）点头像就有哈，里面有个马兰过河卒问题，一模一样的

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
        vector <int> f(m);

        f[0] = (obstacleGrid[0][0] == 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f.back();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

343. 整数拆分

思路：

class Solution {
public:
int integerBreak(int n) {
    return (vector<int>{ -1, -1, 1, 2, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969, 6377292, 9565938, 14348907, 19131876, 28697814, 43046721, 57395628, 86093442, 129140163, 172186884, 258280326, 387420489, 516560652, 774840978, 1162261467, 1549681956  })[n];
}
};
1
2
3
4
5
6

开个玩笑，下面是正八经的思路了：

• 首先dp[i]表示的就是最大的乘积；
• dp公式就是： dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  • 这个咱dp[i]不就是乘积嘛，用这个乘积和 max((i - j) * j, dp[i - j] * j)作比较看看那个大哪个就是dp，那你就问了这个是啥，凭啥能表示
    • 将 i 拆分成 j 和 i-j 的和，且 i-j 不再拆分成多个正整数，此时的乘积是(i - j) * j
    • 将 i 拆分成 j 和 i-j 的和，且 i-j 继续拆分成多个正整数，此时的乘积是dp[i - j] * j
      怎么拆呢，答案就是用j拆，j可能从1到i-1的任何一个数用j来吧i拆成两个数j和i-j。要是还能拆就是j和dp[i-j];因为dp[i-j]肯定是i-j这个点最大的值，所以可以用dp[i-j]来表示这个是拆成多个时候的最大值，当然最大值×肯定是最大的。
      所以就做完了~！

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j < i - 1; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

96. 不同的二叉搜索树

咱讲真，dp的题目看完答案好简单不看答案啥也不会，真服了
初始值：dp[0]=1;dp[1]=1;
循环：
首先1~n中都可以做根节点, for (int i = 2; i <= n; i++)来表示让哪个作为根节点

如果令t为根节点的话那1 ~ t 就会作为左子树（树小）而t ~n个数就作为右子树了（数大）
那首先我们可以fo循环一下让1到n分别为根节点那dp(j-1)*dp(n-j)就是这个节点的个数了
在t点左子树可能有多少种情况？

• 左 1 右 t-1。
• 左 2 右 t-2。
• 左t-1 右 1。

可以看出规律左边的是逐渐递增的怎么表示呢当然是循环了 for (int j = 1; j <= i;j++)

然后 G[i] += G[j - 1] * G[i - j];就可以表示这个为根时的搜索树有多少种结果

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1);
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i;j++) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

卡塔兰数catalan

然后由这个结果我们可以得到一个公式
事实上我们在方法一中推导出的 G(n)函数的值在数学上被称为卡塔兰数
​卡塔兰数更便于计算的定义如下

然后这个题就可以这么做

class Solution {
public:
    int numTrees(int n) {
        long long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)C;
    }
};

1
2
3
4
5
6
7
8
9
10
11

这个数还能解决什么问题呢？

复制的百度哈

---

​​

Love is worth years.❤
热爱可抵岁月漫长。
​​​​
本文部分思路来源于网络如有侵权联系删除~