# 动态规划相关题目

动态规划适合处理一些有重叠子问题的情况。它的每一个步骤都是由上一个状态推导出的。
其核心是通过状态转移公式（递推）来找到结果。

步骤

确定 DP 数组，以及其下标含义
确定状态转移公式
确定 DP 数组初始化策略
确定遍历顺序
举例推导 DP 数组

背包问题
背包类问题是一种经典的动态规划问题。它的核心要素是有最大容量的背包；有不同价值和重量的物品；和物品可用数量，背包可以存放的物品最大总重量。题目要求装最大价值物品的存放方案。
当每个物品只有一件时，称为 0-1 背包；当物品有无限多时，称为完全背包；当不同物品有不同数量时，称为多重背包；当物品按组打包并且每组只能选一个时，称为分组背包。当然这些背包问题可以进行混合出题。

0-1 背包
对于 0-1 背包，每一个物品只有放或者不放两种操作。
方法一：二维 DP 数组
1. 确定 DP 数组以及其下标含义
  我们的状态转移数组采用二维数组的形式。其行数物品种类数，列数表示背包可以容纳的总重量。也就意味着每一行代表物品 i, 每一列代表假设当前背包已经放了重量为 j 的物品。最后一列表示题目目标的包大小，前面的所有列可以认为是容量更少一些的子包。通过子包之间的组合可以凑成更大的包。所以 dp[i][j] 中存放的数字就表示：取物品 i 来判断它放到或不放到最大承重为 j 的子背包中时，背包中物品的最大价值。
  
  数组是循环遍历得出结果的，比如先选定物品，再依次遍历每一种子背包；之后再选下一种物品，再依次遍历每一种子背包；以此循环。
2. 确定状态转移公式
  那么对于 dp[i][j] 中数字来源，认为是物品 i 放入与不放入两种可能组成的。
  
  其中不放入就是对于当前子背包来说，这个物品已经超过了它的最大限制，所以这个子背包在不放入这个物品时的价值就是之前的价值。也就是 dp[i - 1][j].（即对于同样重量的子包，当它在判断上一个物品时的状态）
  
  当要放入该物品时，其逻辑是：当前子包最多可以放的重量是 j, 当前物品重量是 weight[i], 那么当前子包除了当前物品以外还能放下 j - weight[i] 的重量。所以只要找到：在判断上一个物品时，能装下 j - weight[i] 的子包里的价值再加上当前物品的价值，就是对于当前子包放入该物品的总价值。即 dp[i - 1][j - weight[i]] + value[i].
  
  结合上面两点，只要找到放入该物品后的价值和不放该物品的价值，取它们中价值最大的，就是当前物品当前子包的价值。即 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
3. 确定 DP 数组初始化策略
  对于子包最大承重为 0 的状态，设置其物品价值也为 0. 即 dp[i][0] = 0;
```
for (int i = 0; i < itemQuan; i++) {
    dp[i][0] = 0;
}
```
  1
  2
  3
  对于第一个物品，即 i = 0 时，分为两种情况：当子包最大承重比第一个物品重量小时 (j < weight[0])，其价值为 0, 因为该物品无法放入。即 dp[0][j] = 0;; 当子包最大承重比第一个物品重量大或相同时 (j >= weight[0])，其价值就是第一个物品的价值。即 dp[0][j] = value[0].
```
// 分段设置
for (int j = 0; j < weight[0]; j++) {
   dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagCap; j++) {
    dp[0][j] = value[0];
}
```
  1
  2
  3
  4
  5
  6
  7
  其余元素初始化为任意值均可，因为它们会被覆盖。
4. 确定遍历顺序
  根据状态转移公式，我们可以观察出，对于当前 dp[i][j], 影响它的元素是其正上方的 dp[i - 1][j] 和 dp[i - 1][j - weight[i]]. 其中第二个影响元素也在 dp[i][j] 的左上方向。所以对于背包和物品先后遍历次序无影响。
方法二：一维滚动 DP 数组
1. 确定 DP 数组以及其下标含义
  在之前二维数组的基础上，可以采用滚动复制的方法来缩减一个维度。dp[j] 依然表示取物品 i 来判断它放到或不放到最大承重为 j 的子背包中时，背包中物品的最大价值。这里 i 在 for 循环中体现而不单独做一个数组维度。
2. 确定状态转移公式
  类似之前，当外层循环固定物品 i 时，当前最大承重为 j 的子包可以有放或者不放两种可能。
  
  当不放时，其包内物品价值不更新，仍为 dp[j]；
  若放，则考虑这样的逻辑：当前物品的重量是 weight[i], 当前子包最大承重是 j. 如果放了这个物品，为了凑齐 j，我们只需要找到放满 j - weight[i] 的子包的情况。
  取两个的价值相加即为当前子包放入物品 i 后的价值。即 dp[j - weight[i]] + value[i].
  对于放或不放，取它们之间的大者作为结果，即 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3. 确定 DP 数组初始化策略
  dp[0] 表示子包最大承重为 0 时候的包内价值，为 0, 即 dp[0] = 0;
  
  其余为 0.
4. 确定遍历顺序
  为了防止状态重合，对于每个物品，背包的遍历是从后向前的。
```
for (int i = 0; i < itemQuan; i++) {
    for (int j = bagCap; j >= weight[i]; j--) {
        // ...
    }
}
```
  1
  2
  3
  4
  5
完全背包
当物品有无限多个时，是完全背包问题。
对于前面的问题，当把条件改成

# 组合总和 Ⅳ LeetCode 377

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例1
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例2
输入：nums = [9], target = 3
输出：0

[分析]

确定 DP 数组和其下标含义
DP 数组存放构成加和为各 i 的排列数。如 dp[i] 表示由给定数组凑出和为 i 的排列数量。
确定状态转移公式
例如：给定数组[1, 2, 3, 4] 求目标和为 10 的所有组合数量。
对于 dp[5], 即可以凑成和为 5 的所有组合数量，可由 dp[5 - nums[j]] 得出。
假设当前判断到了 nums[1]，即 2. dp[5] 可由 dp[5 - 2] = dp[3] 推导出。理解为已经确定有 2 时，只需要得知 dp[3] 的情况即可凑出 5.
所以最终结果中是需要 dp[3] 的。
我们需要对 nums[] 每一个元素进行这样的遍历来查看具体需求，得到结果后进行累加，最终得到最后结果。
即当取 nums[0] 时，有 nums[0] = 1, dp[5] 需要 dp[5 - 1] = dp[4]，累加；
当取 nums[1] 时，有 nums[1] = 2, dp[5] 需要 dp[5 - 2] = dp[3]，累加；
当取 nums[2] 时，有 nums[2] = 3, dp[5] 需要 dp[5 - 3] = dp[2]，累加；
当取 nums[3] 时，有 nums[3] = 4, dp[5] 需要 dp[5 - 4] = dp[1]，累加；
即 dp[5] = dp[4] + dp[3] + dp[2] + dp[1]
故对指定 i, 内层对 nums 每一个元素的遍历循环有： dp[i] += dp[i - nums[j]]
确定初始值
dp[0] = 1;
遍历顺序
外层从 1 到 target 顺序遍历；内层对 nums 顺序遍历
打印 DP 数组
[1, 1, 2, 4, 7]

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // DP 数组
        int[] dp = new int[target + 1];

        // 初始化
        dp[0] = 1;

        // 动态规划
        for (int i = 1; i <= target; i++) {     // 对于每一个和结果
            for (int num : nums) {              // 遍历 nums 数组
                if (num <= i) {             // 只要元素不大于指定和，肯定都是结果的一部分
                    dp[i] += dp[i - num];   // 累加
                }
            }
        }

        return dp[target];
    }
}

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

# 斐波那契数 LeetCode 509

斐波那契数，通常用 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

解法1
简单递归。

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }
}

1
2
3
4
5
6
7
8
9

解法2
通过动态规划解决。
[分析]

DP 数组
定义数组 dp[]，其中第 i 个元素 dp[i] 表示第 i 个斐波那契数
状态转移公式
dp[i] = dp[i - 1] + dp[i - 2]
初始化 DP 数组
dp[0] = 0;
dp[1] = 1;
遍历顺序
为了 dp[i] 可以取到它之前的 i-1 和 i-2, 应当从前向后遍历
打印 DP 数组
[0, 1, 1, 2, 3, ...]

class Solution {
    public int fib(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];
    }
}

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

解法3
利用三个变量来维护 i, (i - 1) 和 (i - 2).

class Solution {
    public int fib(int n) {
        int num1 = 0;
        int num2 = 1;
        int sum = 0;

        if (n < 2) {
            return n;
        }

        for (int i = 1; i < n; i++) {
            sum = num1 + num2;
            num1 = num2;
            num2 = sum;
        }
        return sum;
    }
}

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

# 爬楼梯 LeetCode 70

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

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

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

示例1
输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

示例2
输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

解法1
类似组合总和 Ⅳ, 这里对应和的结果为 n, nums 数组元素为 1 和 2.

class Solution {
    public int climbStairs(int n) {                 // 完全背包问题
        int[] dp = new int[n + 1];                  // 滚动数组
        int[] stairs = {1, 2};

        dp[0] = 1;

        for (int i = 1; i <= n; i++) {              // 遍历每一种楼梯
            for (int j = 0; j <= 1; j++) {          // 有 1 节和 2 节两种选法
                if (i >= stairs[j]) {               // 只要总台阶数量比 1 或 2 大
                     dp[i] += dp[i - stairs[j]];    // 当已经有 1 或 2 节时，只需要找到能凑齐 i 个台阶就行
                }
            }
        }

        return dp[n];
    }
}

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

解法2
对于一节台阶 i 来说，只有两种来源，就是通过爬一节上来的 dp[i - 1] 和爬两节上来的 dp[i - 2].
那么这道题就转化成了斐波那契数列。

class Solution {
    public int climbStairs(int n) {
       if (n < 2) {
            return n;
        }

        // 动态规划
        int[] dp = new int[n + 1];
        
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

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

# 不同路径 LeetCode 62

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

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

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

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

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

向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下

解法

class Solution {
    public int uniquePaths(int m, int n) {
        // 到位置 (i, j) 有几种路径
        int[][] dp = new int[m][n];

        // 初始化，第一行和第一列只有一种路径
        for (int i = 0; i < m; i++) {   // 列
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {   // 行
            dp[0][i] = 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];
    }
}

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

# 使用最小花费爬楼梯 LeetCode 746

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例 2
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

解法

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 登到台阶 i 需要的体力
        int[] dp = new int[cost.length];

        // 初始化 DP 数组
        dp[0] = cost[0];
        dp[1] = cost[1];

        // 动态规划
        for (int i = 2; i < cost.length; i++) {
            // 状态转移
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        
        // 最后两节不消耗体力
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}

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

← 回溯算法相关题目