微弱的光
0%

动态规划专项训练

发表于 更新于 9.4k 9 分钟

动态规划专项训练

参考：代码随想录官⽹www.programmercarl.com

更新记录

第一次更新 2024.05.13

第二次更新 2024.05.17

一般解题步骤

  1. 确定dp数组（dp table）以及下标的含义

​ dp数组（状态转移数组）可以是一维的可以是二维的

  1. 确定递推公式 （状态转移方程）
  2. dp数组如何初始化
  3. 确定遍历顺序
  4. 举例推导dp数组

实战训练

基础问题

1.斐波那契数

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

1
2
3
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1
2
3
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

1
2
3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

code：

用模拟的思想做的，非dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;
    let num1 = 0, num2 = 1;
    let cur;
    for(let i = 2; i <= n; i++){
        cur = num1 + num2;
        num1 = num2;
        num2 = cur;
    }
    return cur;  
};

用动态规划来做

  1. 确定dp数组（dp table）以及下标的含义

    dp[i]表示第i个斐波那契数

  2. 确定递推公式

    题目 中有 dp[i] = dp[i - 1] + dp[i - 2]

  3. dp数组如何初始化

    题目中有 dp[0] = 0 , dp[1] = 1

  4. 确定遍历顺序

    是从后向前还是从前向后，是一层还是两层，如果是两层，哪层在外面

  5. 打印推导dp数组（debug用的）

70. 爬楼梯

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

code：

在前面知识的基础上，我大概能了解到迈上第n阶的方法其实是有前面的迈上n-1和迈上n-2阶的种数有关的，但是如果没有关键点的想，很容易想岔去。

下面的代码是我第一个自己思考的代码，是错误的，一开始想的是想的是比如想要到第4阶，有可能是dp[1] + dp[3], dp[2]+ dp[2], dp[3] + dp[1]；但是如果这样想的话，所有种类中是会有重复值的。所以我也想到了要去重，但是去重的规律并没有找对；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    //dp[i]表示爬到i阶楼梯，有dp[i]种方法
    let dp = [0, 1, 2];
    //初始化dp[]
    //状态转移方程
    for(let i = 3; i <= n; i++){
        let cn = 0;
        for(let k = 1; k < i; k++){
            cn += (dp[k] * dp[i - k]);
        }
        //去除重复值
        cn = cn - 2 * i + 5;
        dp.push(cn);
    }
    return dp[n];
};

看了卡哥的视频解说，反复想了一下理解了，其实思路是可以有很多种的，但是如果想用动态规划的思路来写，关键点在于状态转移，如果从0阶开始向上迈，那么状态转移方程其实很不好把握，容易像我之前一样想岔了，会想：先走几阶有几种方法，后走几阶有几种方法，很容易把自己绕进去。

但是如果想要专注于状态转移，应该从台阶上往下看，而且必须注意状态转移的条件（即每次只能爬1或2个台阶），那么对于一个人来说，他走到n层台阶的上一个状态只可能有两种：

  1. 上一个状态是走到了n-1个台阶，他是迈了一步才走到n台阶的
  2. 上一个状态是走到了n-2个台阶，他是迈了两步才走到n台阶的

可以想到，这样递归出来的种类数其实是很干净的，不会存在重复值，因为不同于我第一次的想法，我第一次想的是（**step1:**从0-k有几种方法； **step2:**从k-n有几种方法），而动态规划中，强制了我的step2只能有一种方法。举个例子:

易得dp[1] = 1, dp[2]= 2

如果我想求dp[4]

先看看我原本的想法：可能性有先走一步，再走三步；先走二步，再走两步；先走三步，再走一步

那么这个dp[4]=dp[1]*dp[3]+ dp[2]*dp[2]+dp[3]*dp[1]，但是这样的递归推导是不干净的，因为里面存在了很多的重复值

再看看动态规划的思想：如果我想根据step1+step2的思路来思考的话，首先强制step2的方法只能有一种，即当走过step1方法到达中间的某个台阶后，我只能通过一种方法来到达台阶n。

虽然step只能有一种方法，但是step可以有两种情况：即先走 2步，然后走2步到n；或者先走3步，然后走1步到n；

由此可得到：dp[4] = d[2] * 1 + d[3] * 1;

所以我才得出了dp的关键在于：到达这个状态的上一个状态是怎么样的，因为上一个状态总是通过一次操作（一次状态转移）达到这个状态，这样递归下来的数据才是干净的。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    //dp[i]表示爬到i阶楼梯，有dp[i]种方法
    let dp = [0, 1, 2];
    //状态转移方程
    for(let i = 3; i <= n; i++){
        dp.push(dp[i - 1] + dp[i - 2]);//可以不用维护数组，直接用变量来写，写法上一题斐波那契数写法一致，不写了这里
    }
    return dp[n];
};

使用最小花费爬楼梯

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

Code:

这道题的难点在于搞清楚ct[i]到底指的是什么？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} cost
 * @return {number}
 */

//ct[i]指的是到达i（此时i是楼顶）的最小消费
var minCostClimbingStairs = function(cost) {
    //ct[i]达到i台阶的需要最小消费
    if(cost.length==1) return cost[0];
    if(cost.length==2) return Math.min(cost[0],cost[1]);
    let ct1 = Math.min(cost[0],cost[1]);
    let ct = [0, 0];
    for(let i = 2; i <= cost.length; i++){
        let cur = Math.min(ct[i - 1]+cost[i - 1], ct[i-2]+cost[i-2]);
        ct.push(cur);
    }
    return ct[ct.length - 1];
};

不同路径【Mid】

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2
输入：m = 7, n = 3
输出：28

示例 4：

1
2
输入：m = 3, n = 3
输出：6
用dp来写

code

d[x][y]表示从start开始到点（x,y）有d[x][y]种走法

关键点在于只能向下走或者向右走，所以x和y都智能递增，是不可能回头的，所以对于边缘d[x][1]和d[1][y]都应该初始化为1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    //初始化d[x][y]边缘元素为1
    let d = new Array(m + 1);
    for(let x = 1; x <= m; x++){
        d[x] = new Array(n + 1);
        if(x == 1) d[1].fill(1);
        d[x][1] = 1;
    }
    for(let x = 2; x <= m; x++){
        for(let y = 2; y <= n; y++){
            d[x][y] = d[x][y - 1] + d[x - 1][y];
        }
    }
    console.log(d);
    return d[m][n];
};
DFS的基本写法

在JavaScript中，深度优先搜索（DFS）的一般写法与其他编程语言类似。下面是一个基本的DFS函数示例，用于在一个图或树结构中进行深度优先搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function dfs(node, visited) {
    if (visited.has(node)) {
        return;
    }
    
    // 处理当前节点
    visited.add(node);
    
    // 遍历当前节点的相邻节点
    for (let neighbor of node.neighbors) {
        if (!visited.has(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

// 初始化访问记录
let visited = new Set();

// 从起始节点开始进行DFS
dfs(startNode, visited);

在这段代码中，dfs()函数表示深度优先搜索的递归函数，接受一个节点node和一个记录访问情况的visited集合作为参数。在DFS过程中，首先检查当前节点是否已经被访问过，如果已经访问过则直接返回；否则将当前节点标记为已访问，并递归地对当前节点的相邻节点进行DFS遍历。

用dfs,会超时，时间复杂度会达到2^(m+n)次，所以不合适，但是思路是可行的，如果m和n较小的话

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    function dfs(x, y) {
        // 如果越界，则认为这条路径不可行
        if (x >= m || y >= n) return 0;
        // 当到达终点时，返回1
        if (x === m - 1 && y === n - 1) return 1;
        // 向右走 + 向下走
        return dfs(x + 1, y) + dfs(x, y + 1);
    }

    return dfs(0, 0);
};

不同路径II

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

img

1
2
3
4
5
6
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

1
2
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    //当（x,y）点是障碍点时，那么达到x,y的路径只能是0条，多加一个判断条件
    //初始化d[x][y]
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let d = new Array(m);
    for(let x = 0; x < m; x++){
        d[x] = new Array(n);
        let y = 0;
        while(x==0 && obstacleGrid[0][y]!=1 && y < n){
            d[0][y++] = 1
        }
        while(x==0 && y < n){
            d[0][y++] = 0;
        }
        if(obstacleGrid[x][0]!=1){
            d[x][0] = 1;
        } else {
            while(x < m){//这里有个易错点
              //如果在这个代码块种不加if(x < m)d[x] = new Array(n);，那么因为当x++的时候，下一个d[x]是没有定义为数组的，如果此时使用d[x][0]就会报不能给undefined赋值的错误
                d[x][0] = 0;
                x++;
                if(x < m)d[x] = new Array(n);
            }
        }     
    }
    for(let x = 1; x < m; x++){
        for(let y = 1; y < n; y++){
            if(obstacleGrid[x][y]==1){
                d[x][y] = 0;
            }else{
                d[x][y] = d[x-1][y] + d[x][y-1];
            }
        }
    }
    console.log(d);
    return d[m-1][n-1];

};

整数拆分

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

1
2
3
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

1
2
3
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

  • 2 <= n <= 58

code：

把数尽量拆成平均的

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    let maxNum = -1;
    for(let k = 2; k <= n ; k++){
        let m = n % k;//余数
        maxNum = Math.max(((((n-m)/k) + 1))**(m) * (((n-m)/k)) ** (k - m), maxNum);
    }
    return maxNum;
};

dp思想:对于递推公式还是有点疑惑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    // 10 
    //  1 9
    // 2 8 
    // 3 7
    //4 6
    // 5 5
    // 6 4
    // 7 3
    // 8 2
    // 9 1
    let dp = new Array(n+1).fill(0);//要先提前初始化为0
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    // 3  
    for(let i = 3; i <= n; i++){
        for(let j = 1; j <= i/2; j++){
            dp[i] = Math.max(j*(i-j), j*dp[i-j],dp[i]);
        }
    }
    return dp[n];

};

不同的二叉搜索树

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

img

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 19

Code:

如果清楚二叉搜索树的特性和知道用动态规划来做这道题，这道题其实还不算特别难，但是需要画图分析一下，其实就是找规律的过程。

由于二叉搜索树的特性（比跟节点小的数一定放在左子树中，比根节点大的数一定放在右子树中），所以就需要考虑当j作为根节点的时候，会有几种情况，在对j从0遍历到n；这里为什么从0开始遍历，后面会解释。

在实际分析前，需要注意的一点的，如果一棵树只有3个节点，那无论这三个节点里面的数是（1，2，3），还是（2，3，4），或者是（11，12，13）等等，只要是连续的数字，那么他们的二叉搜索树的种类个数就一定是相等的。即树有几种可能性是考虑树中有几个节点，而不是考虑树中节点的实际值。

具体来说，考虑n=4的情况，在n=4时，分为4种情况讨论：

  • 当root=1，那么可以得知对于2，3，4节点来说，这三个节点都将放在以1为根节点的树的右子树下，因为 2，3，4都大于1，那么对于右子树而言，只需要计算（2，3，4）节点的可能种类即d[3];在考虑左子树，由于没有比1还小的树节点，所以此时的左子树是为空的，即d[0]。一般来说，如果考虑d[0]的实际意义，可能会给d[0]赋值为0;

    但是需要考虑到，一棵树的种类，如果确定了根节点，那么这颗树的可能种类就是左子树的可能种类个数乘上右子树的可能种类个数，即d[3]*d[0]，如果我们给d[0]赋值为0，那么d[3]*d[0]==0，这很明显和实际情况不符。再加上题目中1<=n<=19，所以我们不妨将d[0]赋值为1。

  • 那么当roo=2，我们同理分析，只有（1）节点(1个节点)在右子树中，而（2,3）节点（2个节点）在左子树中，那么可能性就是d[1]*d[2]

  • 同理，当root=3，有（1，2）2个节点在右子树，只有（4）1个节点在左子树中，所以可能性是d[2]*d[1]

  • 当root=4，有(1,2,3)3个节点在右子树，0个节点在左子树，即d[3]*d[0]

    总结分析得 root==1 d[3]*d[0]

    总结分析得 root==2 d[2]*d[1]

    总结分析得 root==3 d[1]*d[2]

    总结分析得 root==4 d[0]*d[3]

    ​ 即 root==j d[i-j-1]*d[j]，j从0到i-1（0和i-1都去得到）

    从实际意义上来理解其实也很好，如果是一颗有i个节点的树，其中一个节点已经确定了是根节点了，所以只有剩下的i-1个节点分别分配在左右子树中，所以左右子树的节点个数相加是i-1，所以上面的d[i-j-1]*d[j]中的i-j-1加上j是一定等于i-1的。

现在只需要对上面的4种情况（i==4种情况)进行求和就可以得出dp[4]即dp[i]

这种规律从i=3就开始了，所以可以从i=3开始遍历，一直到题目所求的i==n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    //d[i]表示有i个节点的二叉搜索树的种数
    let dp = new Array(n+1).fill(1);
    dp[2] = 2;
    for(let i = 3; i <= n; i++){
        let cn = 0;
        for(let j = 0; j < i; j++){
            cn += (dp[j] * dp[i-j-1]);
        }
        dp[i] = cn;
    }
    return dp[n];
};

背包问题

416. 分割等和子集

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路

取和不取的问题，对于一个正数数组，数组中所有值的和事确定的，所以分成两个子集后，两个子集的元素和就为整个和的一半

-------------本文结束感谢您的阅读-------------
原创技术分享，您的支持将鼓励我继续创作