Skip to content

09. Dynamic Programming（动态规划）

0、 基础理论

动态规划（Dynamic Programming）是计算机科学中一个重要的概念，它描述了如何解决复杂的问题，通过分解问题，将原问题分解为若干个子问题，然后通过解决子问题来求解原问题。

动态规划的核心思想是：将问题分解为若干个子问题，然后通过解决子问题来求解原问题。既：动态规划中每一个子问题的状态一定是由上一个或多个子问题的状态推导出来的。

例如：有 N 件物品和一个最多能背重量为 W 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中 dp[j] 是由 dp[j - weight[i]]推导出来的，然后取 max(dp[j], dp[j - weight[i]] + value[i])。

但在贪心算法中，每次拿物品选一个最大的或者最小的就完事，和上一个状态没有关系。

0.1、 解题步骤

动态规划解题五部曲：

  1. 确定 dp 数组（dp table）以及下标的含义；
  2. 确定递推公式；
  3. dp 数组如何初始化；
  4. 确定遍历顺序；
  5. 举例推导 dp 数组。

切记死记公式，依葫芦画瓢

0.2、 如何调试

当代码运行出现问题时，找问题的最好方式就是把 dp 数组打印出来，看看究竟是不是按照自己思路推导的！

写代码之前一定要把状态转移在 dp 数组的上具体情况模拟一遍，做到心中有数，确定最后推出的是想要的结果。

然后再写代码，如果代码没通过，就打印 dp 数组，看看是不是和自己预先推导的不一样，哪里有差异。

  • 如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了；
  • 如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改。

1、 斐波那契数列

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：0 <= n <= 30

思路

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义，
dp[i]的定义为：第 i 个数的斐波那契数值是 dp[i]
  1. 确定递推公式，
题目中已经给出了递推公式：dp[i] = dp[i-1] + dp[i-2]
  1. dp 数组如何初始化，
题目中也已给出初始化条件：dp[0] = 0, dp[1] = 1
  1. 确定遍历顺序，
从递推公式可知，dp[i]是依赖 dp[i-1] 和 dp[i-2]，那么遍历的顺序一定是从前到后的
  1. 举例推导 dp 数组，
按照这个递推公式，当N为10的时候，dp 数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55

解答

    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int fibonacci(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 空间优化版本
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int fibonacciOptimized(int n) {
        if (n < 2) return n;
        int[] dp = new int[]{0, 1};
        int sum;
        for (int i = 2; i <= n; i++) {
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }

2、 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有 2 种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶

示例 2：

输入： 3
输出： 3
解释： 有 3 种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

思路

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义，
dp[i]的定义为：上到第 i 层台阶的方法数
  1. 确定递推公式，
因为一次可以上 1 层或者 2 层，那么上到第 i 层的方法数，就应该是 到达 i-1 层的方法数和到达 i-2 层方法的数之和。既：dp[i] = dp[i-1] + dp[i-2]
  1. dp 数组如何初始化，
当 i=0 时，可以理解为还没有开始上楼，那么初始化 dp[0] = 0；而从示例中也可以推导出 dp[1] = 1，只有一种方法可以到达第一层；dp[2] = 2，有两种方法可以到达第二层
  1. 确定遍历顺序，
从递推公式可知，dp[i]是依赖 dp[i-1] 和 dp[i-2]，那么遍历的顺序一定是从前到后的
  1. 举例推导 dp 数组，
按照这个递推公式，当 n 为 5 的时候，dp 数组应该是如下的数列：
    i = 0 1 2 3 4 5
dp[i] = 0 1 2 3 5 8

提示：本题中说明 n 是一个正整数，因此 dp[0] 没有意义，初始化为 int 默认值 0 即可，争论其表示的含义，没有意义。

解答

    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 空间优化版本同斐波那契数列

3、 最小花费爬楼梯

给定一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

最小花费爬楼梯

思路

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义，
dp[i]的定义为：上到第 i 层台阶所花费的最小代价
  1. 确定递推公式，
依题意，有两个途径可以到达第 i 层，一个是dp[i-1] 一个是dp[i-2]，则需要的花费就是到达上一层的最小花费加上到此层需要支付分花费。既，
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  1. dp 数组如何初始化，
dp[i]由dp[i-1]，dp[i-2]推出，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]和dp[1]推出。
描述中明确说了“可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达 第 0 个台阶是不花费的，但从第 0 个台阶往上跳的话，需要花费 cost[0]。
所以初始化 dp[0] = 0，dp[1] = 0;
  1. 确定遍历顺序，
从递推公式可知，dp[i]是依赖 dp[i-1] 和 dp[i-2]，那么遍历的顺序一定是从前到后的
  1. 举例推导 dp 数组，
按照这个递推公式，使用示例2中的数组来模拟，cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]，dp 数组应该是如下的数列：
 cost = 1 100 1 1 1 100 1 1 100 1 TOP
    i = 0   1 2 3 4   5 6 7   8 9  10
dp[i] = 0   0 1 2 2   3 3 4   4 5   6

解答

    public static int minCostClimbStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }

4、 不同路径

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

不同路径

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：m = 3, n = 3
输出：6

提示：1 <= m, n <= 100，题目数据保证答案小于等于 2 * 10 的 9 次幂

思路

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义，
dp[i][j]的定义为：表示从（0 ，0）出发，到(i, j) 的路径数
  1. 确定递推公式，
依题意机器人只能从上向下，从左向右移动，所以到达(i, j)位置只有两条路径，则有：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  1. dp 数组如何初始化，
网格的左边和上边的路径只有一条，既：dp[0][j] = 1, dp[i][0] = 1
  1. 确定遍历顺序，
从递推公式可知，dp[i][j]都是从其上方和左方推导而来，那么就从左到右一层一层遍历
  1. 举例推导 dp 数组，
按照这个递推公式，dp 数组应该是如下的数列：
  n→
m 1  1  1  1  1  1  1
↓ 1  2  3  4  5  6  7
  1  3  6 10 15 21 28

解答

    public static int countPaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int k = 0; k < m; k++) {
            dp[k][0] = 1;
        }
        for (int k = 0; k < n; k++) {
            dp[0][k] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

5、 不同路径 II

给定一个 m x n 的整数数组 grid。一个机器人初始位于左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含任何有障碍物的方格。返回机器人能够到达右下角的不同路径数量。

示例 1：

不同路径II示例1

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

示例 2：

不同路径II示例2

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

思路

与上一题不同路径相同，只是增加了障碍物，所以需要增加一个判断，如果当前位置是障碍物，则路径数置为 0，否则路径数等于上方和左方路径数之和。

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义，
dp[i][j]的定义为：表示从（0 ，0）出发，到(i, j) 的路径数
  1. 确定递推公式，
依题意机器人只能从上向下，从左向右移动，所以到达(i, j)位置只有两条路径，但因为有了障碍，(i, j)如果是障碍的话应该设置为0，则有：
if (obstacleGrid[i][j] == 0) {
    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
}
  1. dp 数组如何初始化，
网格的左边和上边的路径只有一条，但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。既：
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
  1. 确定遍历顺序，
从递推公式可知，dp[i][j]都是从其上方和左方推导而来，那么就从左到右一层一层遍历
  1. 举例推导 dp 数组，
按照这个递推公式，dp 数组应该是如下的数列：
  n→
m 1  1  1
↓ 1  0  1
  1  1  2

解答

    public static int countPaths(int m, int n, int[][] obstacleGrid) {
        int[][] dp = new int[m][n];
        for (int k = 0; k < m; k++) {
            Arrays.fill(dp[k], 0);
        }
        for (int k = 0; k < m && obstacleGrid[k][0] == 0; k++) {
            dp[k][0] = 1;
        }
        for (int k = 0; k < n && obstacleGrid[0][k] == 0; k++) {
            dp[0][k] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

6、 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

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

示例 2:

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

提示: 你可以假设 n 不小于 2 且不大于 58。

思路

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义，
dp[i]的定义为：表示拆分正整数 i 后可以获得的最大乘积
  1. 确定递推公式，
既然要进行拆分，那么必然存在两层遍历，i 表示要拆分的数，则 j 表示拆分出的一个正整数，j 可以从1开始遍历，然后有两种方式获取 dp[i]，
    - 直接相乘，j * (i - j)
    - 与 i - j 可获得的最大乘积相乘，j * dp[i - j]
这两个数中取大的，所以地推公式为：
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]))
  1. dp 数组如何初始化，
0和1无法再分，没有意义，所以初始化 dp[2] = 1
  1. 确定遍历顺序，
从递推公式可知，dp[i] 依靠 dp[i - j] 的状态，所以遍历i一定是从前向后遍历，先有 dp[i - j] 再有 dp[i]
  1. 举例推导 dp 数组，
按照这个递推公式，当 n = 10，dp 数组应该是如下的数列：
    i  2  3  4  5  6  7  8  9  10
dp[i]  1  2  4  6  9 12 18 27  36

解答

    public static int splitInt(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }