1.21：动态规划-斐波那契数列

题目：

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

分析：

经典题目，递归入门题，常见做法就是两条递归语句就解决了，但是这道题也可以当做一道经典又简单的动态规划题，从而来理一理动态规划题的解题步骤。

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果。

1. 确定dp数组以及下标的含义
   dp[i]的定义为：第i个数的斐波那契数值是dp[i]。
2. 确定递推公式
   题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i – 1] + dp[i – 2]。
3. dp数组如何初始化
   dp[0] = 0;
   dp[1] = 1;
4. 确定遍历顺序
   从递归公式dp[i] = dp[i – 1] + dp[i – 2];中可以看出，dp[i]是依赖 dp[i – 1] 和 dp[i – 2]，那么遍历的顺序一定是从前到后遍历的。
5. 举例推导dp数组
   按照这个递推公式dp[i] = dp[i – 1] + dp[i – 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
   0 1 1 2 3 5 8 13 21 34 55
   如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

答案（动态规划写法）：

1.22：动态规划-爬楼梯

题目：

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

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

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

示例 1：

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

示例 2：

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

分析：

这道题的思路分析起来还是很有意思的，最后得出来的方法也是让人耳目一新（因为我一开始没看出来:(），而且可以发现动规五部曲的关键在于前两步，第三步算是细节问题（目前看来）。

这道题直接得出思路还是比较难的，我们可以从例子中找找规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

动规五部曲：

定义一个一维数组来记录不同楼层的状态

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

dp[i]： 爬到第i层楼梯，有dp[i]种方法

2. 确定递推公式

如何可以推出dp[i]呢？

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i – 1]，上i-1层楼梯，有dp[i – 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i – 2]，上i-2层楼梯，有dp[i – 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i – 1]与dp[i – 2]之和！

所以dp[i] = dp[i – 1] + dp[i – 2] 。（其实就是斐波那契数列！）

在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性！

3. dp数组如何初始化

因为题目说了n是正整数，所以dp[0] = 0就行了，dp[1] = 1，dp[2] = 2没什么问题。

4. 确定遍历顺序

从递推公式dp[i] = dp[i – 1] + dp[i – 2];中可以看出，遍历顺序一定是从前向后遍历的

5. 举例推导dp数组（略）

答案：

1.23：动态规划-最小花费爬楼梯

题目：

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

你可以选择从下标为 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 。

分析：

有了前两题的铺垫以后，这道动规爬楼题就显得简单了不少，实际上主要就是状态转移公式上的一些区别了。

动规五部曲：

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

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

2. 确定递推公式

dp[i – 1] 跳到 dp[i] 需要花费 dp[i – 1] + cost[i – 1]。

dp[i – 2] 跳到 dp[i] 需要花费 dp[i – 2] + cost[i – 2]。

选最小的，所以dp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i – 2])。

3. dp数组如何初始化

题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯，所以初始化 dp[0] = 0，dp[1] = 0。

4. 确定遍历顺序（略）

5. 举例推导dp数组（略）

答案：

1.24：动态规划-不同路径

题目：

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

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

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

示例 1：

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

示例 2：

• 输入：m = 2, n = 3
• 输出：3

解释： 从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

分析：

首先要注意看题干，只能向下或者向右，这很关键，由此我们可以确定每个位置只可能来源于其上边或左边的位置，这是得出递推公式的关键。

动规五部曲：

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

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

2. 确定递推公式

想要求dp[i][j]，只能有两个方向来推导出来，即dp[i – 1][j] 和 dp[i][j – 1]。

此时在回顾一下 dp[i – 1][j] 表示啥，是从(0, 0)的位置到(i – 1, j)有几条路径，dp[i][j – 1]同理。

那么很自然，dp[i][j] = dp[i – 1][j] + dp[i][j – 1]，因为dp[i][j]只有这两个方向过来。

3. dp数组的初始化

如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。

所以初始化代码为：

for (int i = 0; i < m; i++) dp[i][0] = 1;

for (int j = 0; j < n; j++) dp[0][j] = 1;

4. 确定遍历顺序

这里要看一下递推公式dp[i][j] = dp[i – 1][j] + dp[i][j – 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

5. 举例推导dp数组

答案：

1.25：动态规划-不同路径II

题目：

在上一题的基础上考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

示例1：

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

示例2：

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

分析：

该题作为上题的变式，仅仅增加了一个障碍物而已，实际上也只需要适当地在动规中增加判断即可，同时也要注意初始化情况有所不同。

这里，我们约定：有障碍的话，标记对应的dp数组保持初始值(0)。

动规五部曲：

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

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

2. 确定递推公式

递推公式和之前也一样，dp[i][j] = dp[i – 1][j] + dp[i][j – 1]。（因为障碍物设为0，不会对递推公式有影响）

3. dp数组如何初始化

这里要注意，如果障碍在初始的两条边上，障碍之后（包括障碍）都是走不到的位置。如图：

所以本题初始化代码为：

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;

注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理。

4. 确定遍历顺序

和上题一样，只是要多加一个判断：

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];
    }
}

5. 举例推导dp数组

示例1推导：

答案：

1.26：动态规划-整数拆分

题目：

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

示例 1:

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

示例 2:

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

分析：

这一题的思路算是比较难想到，也比较难想通的，看到这道题目，都会想拆成两个呢，还是三个呢，还是四个….

动规五部曲：

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

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。（时刻谨记）

2. 确定递推公式

从1遍历j，有两种渠道可以得到dp[i]：

一个是j * (i – j) 直接相乘。

一个是j * dp[i – j]，相当于是拆分(i – j)。

可以这么理解：j * (i – j) 是单纯的把整数拆分为两个数相乘，而j * dp[i – j]是拆分成两个以及两个以上的个数相乘。

至于为什么不拆分j，其实在写代码的时候也是可以拆分的，只是我在尝试以后发现时间高了不少，而从逻辑上看也不需要拆分j，具体有两种理解：

1. j * (i – j) 是单纯的把整数拆分为两个数相乘，j * dp[i – j]是拆分成两个以及两个以上的个数相乘，而 dp[i – j] * dp[j] 是默认将一个数强制拆成4份以及4份以上了。

2. 拆分j的情况，在遍历j的过程中dp[i – j]其实都计算过了。例如 i= 10，j = 5，i-j = 5，如果把j拆分为 2 和 3，其实在j = 2 的时候，i-j= 8 ，拆分i-j的时候就可以拆出来一个3了。所以也可以理解j是拆分i的第一个整数。

3. dp的初始化

从题意就可以看出，0和1没有拆分意义，所以不需要给0和1初始化，只需要将2初始化为1就可以了，因为从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议。（在后续代码的编写中可以避免去遍历dp[0/1]，实际上也不需要遍历到dp[1] * j，因为从j * (i – j)这一步看，这一步算是已经被拆过了，重复计算）

4. 确定遍历顺序

dp[i] 是依靠 dp[i – j]的状态，所以遍历i一定是从前向后遍历，先有dp[i – j]再有dp[i]。

遍历可以被优化，包括上一步所说的 i – 1 避免重复计算，但是还有一个定理：拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。

例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。

只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。

那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。

5. 举例推导dp数组

举例当n为10 的时候，dp数组里的数值，如下：

答案：

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

1.27：动态规划-不同的二叉搜索树

题目：

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

分析：

这个题的思路不容易直接想出来，可以从1开始多举例推一推，找找基本规律。

n为1的时候有一棵树，n为2有两棵树，这个是很直观的。

n为3的时候，有哪几种情况。

当1为头结点的时候，其右子树有两个节点，看这两个节点的布局，是不是和 n 为2的时候两棵树的布局是一样的啊！

当3为头结点的时候，其左子树有两个节点，看这两个节点的布局，是不是和n为2的时候两棵树的布局也是一样的啊！

当2为头结点的时候，其左右子树都只有一个节点，布局是不是和n为1的时候只有一棵树的布局也是一样的啊！

（可能会有人问，这布局不一样啊，节点数值都不一样。别忘了我们就是求不同树的数量，并不用把搜索树都列出来，所以不用关心其具体数值的差异）

发现到这里，其实我们就找到了重叠子问题了，其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来dp[3]的某种方式。

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]。

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

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

2. 确定递推公式

在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]。

j相当于是头结点的元素，从1遍历到i为止。

所以递推公式：dp[i] += dp[j – 1] * dp[i – j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量。

3. dp数组如何初始化

只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。（当然，dp[1]也可以初始化一下）

从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。

从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。

所以初始化dp[0] = 1。

4. 确定遍历顺序

首先一定是遍历节点数，从递归公式：dp[i] += dp[j – 1] * dp[i – j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。

那么遍历i里面每一个数作为头结点的状态，用j来遍历。

5. 举例推导dp数组（略）

答案：

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

2.18：背包问题（重要）

题目（01背包）：

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

分析：

解法一：二维数组

动规五部曲（根据子问题的求解推导出整体的最优解）：

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

二维数组为 dp[i][j]，i 来表示物品、j表示背包容量。

2. 确定递推公式

其实对于任何一个格子，都只有两种选择：放和不放该物品。

这里取dp[1][4]的状态来举例：

求取 dp[1][4] 有两种情况：

1. 放物品1
2. 还是不放物品1

如果不放物品1， 那么背包的价值应该是 dp[0][4] 即 容量为4的背包，只放物品0的情况。

如果放物品1， 那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。

容量为1，只考虑放物品0 的最大价值是 dp[0][1]，这个值我们之前就计算过。

所以 放物品1 的情况 = dp[0][1] + 物品1 的价值，推导方向如图：

两种情况，分别是放物品1 和 不放物品1，我们要取最大值（毕竟求的是最大价值）。

以上过程，抽象化如下：

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i – 1][j]。
• 放物品i：背包空出物品i的容量后，背包容量为j – weight[i]，dp[i – 1][j – weight[i]] 为背包容量为j – weight[i]且不放物品i的最大价值，那么dp[i – 1][j – weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。

递归公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化

for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

4. 确定遍历顺序

先遍历 物品 还是先遍历 背包重量 呢？都行，但是从理解上建议先遍历物品（就是物品for循环放外层）。

for (int i = 1; i < n; i++) {
            for (int j = 0; j <= bagweight; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }

解法二：滚动数组（更常用）

对于背包问题其实状态都是可以压缩的。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]);

其实可以发现如果把dp[i – 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j – weight[i]] + value[i]);

与其把dp[i – 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

动规五部曲：

1. 确定dp数组的定义

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2. 确定递推公式

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. dp数组初始化

都初始为0就可以了。

4. 确定遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量（倒序遍历）
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

注意，一维dp遍历的时候，背包是从大到小，倒序遍历。

为什么呢？

倒序遍历是为了保证物品i只被放入一次！一旦正序遍历了，那么物品0就会被重复加入多次！

举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

如果正序遍历

dp[1] = dp[1 – weight[0]] + value[0] = 15

dp[2] = dp[2 – weight[0]] + value[0] = 30

此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 – weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 – weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

再注意，两个嵌套for循环的顺序，必须先遍历物品再遍历背包容量，不可以先遍历背包容量再遍历物品。

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的，这一点一定要注意。

答案：

// 创建一个动态规划数组 dp，初始值为 0
        int[] dp = new int[N + 1];

        // 外层循环遍历每个类型的研究材料
        for (int i = 0; i < M; i++) {
            // 内层循环从 N 空间逐渐减少到当前研究材料所占空间
            for (int j = N; j >= costs[i]; j--) {
                // 考虑当前研究材料选择和不选择的情况，选择最大值
                dp[j] = Math.max(dp[j], dp[j - costs[i]] + values[i]);
            }
        }

2.17：背包问题-分割等和子集

题目：

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

示例 1:

• 输入: [1, 5, 11, 5]
• 输出: true
• 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

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

分析：

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

那么本题的本质是，能否把容量为 sum / 2的背包装满。

这是背包算法可以解决的经典类型题目。

只要想出这一点，就可以直接套01背包的解题模版了。

答案：

2.18：背包问题-最后一块石头的重量II

题目：

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

• 输入：[2,7,4,1,8,1]
• 输出：1

解释：

• 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
• 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
• 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
• 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

分析：

本题其实是尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。

一堆的石头重量是sum，那么我们就尽可能拼成 重量为 sum / 2 的石头堆。 这样剩下的石头堆也是 尽可能接近 sum/2 的重量。 那么此时问题就是有一堆石头，每个石头都有自己的重量，是否可以 装满 最大重量为 sum / 2的背包。

和上一题几乎是一模一样，关键还是要学会把实际问题转换为背包问题。

答案：

2.19：背包问题+组合问题-目标和（难）

题目：

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

• 输入：nums: [1, 1, 1, 1, 1], S: 3
• 输出：5

解释：

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

分析：

这题上来第一个问题就是：看上去和动态规划背包没啥关系。

但是这类题其实可以这样想：

本题要如何使表达式结果为target，

既然为target，那么就一定有 left组合 – right组合 = target。

left + right = sum，而sum是固定的。right = sum – left

left – (sum – left) = target 推导出 left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

按照这个思路分析：

假设加法的总和为x，那么减法对应的总和就是sum – x。

所以我们要求的是 x – (sum – x) = target

x = (target + sum) / 2

此时问题就转化为，用nums装满容量为x的背包，有几种方法。

这里就可以看出对背包问题进行转换是一件非常关键的工作。

这时，我们还要注意题目给的都是整数，而 (target + sum) / 2 可能会向下取整，此时是无解的，例如sum是5，target是2 的话其实就是无解的。

同时如果target 的绝对值已经大于sum，那么也是无解的。

接着就是第二个难点，这是个组合问题，让我们在动规五部曲中慢慢体会。

解法一：二维数组（易于理解）

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

dp[i][j]：使用 0 – i 的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。

2. 确定递推公式（详细过程）

背包中的每个格子都有两种选择：

• 不放物品i：即背包容量为j，里面不放物品i，装满有dp[i – 1][j]中方法。
• 放物品i： 即：先空出物品i的容量，背包容量为（j – 物品i容量），放满背包有 dp[i – 1][j – 物品i容量] 种方法。

本题中，物品i的容量是nums[i]，价值也是nums[i]。

递推公式：dp[i][j] = dp[i – 1][j] + dp[i – 1][j – nums[i]];

注意，j – nums[i] 作为数组下标有为负数的可能，所以递推公式：

if (nums[i] > j) dp[i][j] = dp[i - 1][j]; 
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

3. dp数组如何初始化

递推的方向：由上方和左上方推出。那么二维数组的最上行 和 最左列一定要初始化，这是递推公式推导的基础。

显然，最上行只有背包容量为 物品0 的容量的时候，方法为1，正好装满，其他情况下，要不是装不满，要不是装不下。

最左列的方法都是1，即不放。

但这里有例外，就是如果物品数值就是0呢？

如果有两个物品，物品0为0， 物品1为0，装满背包容量为0的方法有几种。

• 放0件物品
• 放物品0
• 放物品1
• 放物品0 和 物品1

此时是有4种方法。

其实就是算数组里有t个0，然后按照组合数量求，即 2^t 。

初始化如下：

int numZero = 0;
for (int i = 0; i < nums.size(); i++) {
    if (nums[i] == 0) numZero++;
    dp[i][0] = (int) pow(2.0, numZero);
}

4. 确定遍历顺序

从刚刚的递推顺序就可以看出是先从上到下，再从左到右遍历，这样也就确定了两个for的书写。

解法二：一维滚动数组（常用书写）

1. 和之前做的一样，就是压缩二维数组，dp[i][j] 去掉行的维度，即 dp[j]，表示：填满j（包括j）这么大容积的包，有dp[j]种方法。

2. 二维DP数组递推公式： dp[i][j] = dp[i – 1][j] + dp[i – 1][j – nums[i]];

去掉维度i 之后，递推公式：dp[j] = dp[j] + dp[j – nums[i]] ，即：dp[j] += dp[j – nums[i]]; （在求装满背包有几种方法的情况下，递推公式一般都为：dp[j] += dp[j - nums[i]];）

3. 这里只需要将 dp[0] 初始化为1就可以了。

4. 一维滚动数组的遍历顺序很重要，一定是：遍历物品放在外循环，遍历背包在内循环，且内循环倒序（为了保证物品只使用一次）。

答案：

2.20：二维背包问题-一和零（较难）

题目：

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

示例 1：

• 输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
• 输出：4
• 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10″,”0001″,”1″,”0”} ，因此答案是 4 。 其他满足题意但较小的子集包括 {“0001″,”1”} 和 {“10″,”1″,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

• 输入：strs = [“10”, “0”, “1”], m = 1, n = 1
• 输出：2
• 解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

分析：

这个题的关键在于想清楚：

strs 数组里的元素就是物品，但是物品有两个维度，所以相应的背包也要有两个维度。

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

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

2. 确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i – zeroNum][j – oneNum] + 1，1是这个字符串的value（每个字符串的value都是1）。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i – zeroNum][j – oneNum] + 1);

此时可以回想一下01背包的一维滚动数组的递推公式：dp[j] = max(dp[j], dp[j – weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

3. 一维dp数组初始化为0就可以了

4. 确定遍历顺序

同样，遍历物品放在外循环，遍历背包在内循环，且内循环倒序。

答案：

2.21~2.22：完全背包问题+组合问题-零钱兑换II

题目：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

• 输入: amount = 5, coins = [1, 2, 5]
• 输出: 4

解释: 有四种方式可以凑成总金额:

• 5=5
• 5=2+2+1
• 5=2+1+1+1
• 5=1+1+1+1+1

示例 2:

• 输入: amount = 3, coins = [2]
• 输出: 0
• 解释: 只用面额2的硬币不能凑成总金额3。

分析：

首先，这是个典型的背包问题：给出一个总数，一些物品，问能否凑成这个总数。

其次，与01背包不同的是，物品有无限个，那么就是典型的完全背包问题了。

最后，本题求的是装满这个背包的物品组合数是多少，所以这还是一个组合问题。（注：组合 ≠ 排列，区别在于是否在乎顺序）

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

 dp[i][j]：使用下标为0-i的coins[i]能够凑满j这么大容量的包，有dp[i][j]种组合方法。（是不是和上一道组合题很相似）

2. 确定递推公式

完全背包问题和01背包问题的差别之一就在这里：

01背包二维DP数组的递推公式为：

dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i])

完全背包二维DP数组的递推公式为：

dp[i][j] = max(dp[i – 1][j], dp[i][j – weight[i]] + value[i])

主要原因就是完全背包单类物品有无限个，所以并不会向上层寻找。（如果不理解，详细可见这里）

3. dp数组如何初始化

和上一道目标和一样，都是初始化最上行 和 最左列：

不一样的是，因为题目规定了coin >= 1，所以最左列就是1，即不放。

而最上行，如果 j 可以整除 物品0，那么装满背包就有1种组合方法。

for (int j = 0; j <= bagSize; j++) {
    if (j % coins[0] == 0) dp[0][j] = 1;
}

4. 遍历顺序与 目标和 一致，两个for循环顺序无所谓。

解法二：一维滚动数组

1. dp[j]：凑成总金额j的货币组合数为dp[j]。

2. 确定递推公式

本题 二维dp 递推公式： dp[i][j] = dp[i – 1][j] + dp[i][j – coins[i]]

压缩成一维：dp[j] += dp[j – coins[i]]。

和之前的组合问题 目标和 一致。

3. 初始化：dp[0] = 1

4. 确定遍历顺序

这里又要注意了，在01背包中，一维滚动数组必须遵守：先物品、后容量、内倒序的遍历顺序，但在纯完全背包问题中，一维滚动数组的两个for循环顺序是无所谓的，并且内循环是顺序的。

但是！因为本题要求凑成总和的组合数，元素之间明确要求没有顺序，所以两个for循环的先后顺序是有说法的！

先来看外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况：

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数！

如果把两个for交换顺序，代码如下：

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况（可以想象成 1 5 1 5 交叉排列组合的情形）。

此时dp[j]里算出来的就是排列数！

如果求组合数就是外层for循环遍历物品，内层for遍历背包（把物品按顺序一个一个加入计算，就不会出现排列组合的情况）。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

答案：

2.23：完全背包问题+排列问题-组合总和 Ⅳ

题目：

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

分析：

抽象题目，问的是组合，实际上是排列，如果充分理解了上一题的思路，这题完全没有难度，只是遍历顺序的变更罢了：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

答案：

2.24：完全背包问题+排列问题-爬楼梯（进阶版）

题目：

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

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

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

输入描述：输入共一行，包含两个正整数，分别表示n, m

输出描述：输出一个整数，表示爬到楼顶的方法数。

输入示例：3 2

输出示例：3

提示：

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

• 1 阶 + 1 阶 + 1 阶段
• 1 阶 + 2 阶
• 2 阶 + 1 阶

分析：

一眼完全背包问题+排列问题，就是换了个题面，需要转换一下罢了，解法和上一题几乎是一模一样。

答案：

class climbStairs{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            n = sc.nextInt();
            m = sc.nextInt();

            // 求排列问题，先遍历背包再遍历物品
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }

            System.out.println(dp[n]);
        }
    }
}

2.25：完全背包问题+求最小数-零钱兑换

题目：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

• 输入：coins = [1, 2, 5], amount = 11
• 输出：3
• 解释：11 = 5 + 5 + 1

示例 2：

• 输入：coins = [2], amount = 3
• 输出：-1

分析：

题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。

1. dp[j]：凑足总额为j所需钱币的最少个数为dp[j]。

2. 确定递推公式

凑足总额为j – coins[i]的最少个数为dp[j – coins[i]]，那么只需要加上一个钱币coins[i]即dp[j – coins[i]] + 1就是dp[j]。

所以dp[j] 要取所有 dp[j – coins[i]] + 1 中最小的。

递推公式：dp[j] = min(dp[j – coins[i]] + 1, dp[j]);

3. dp数组如何初始化

显然凑足总金额为0所需钱币的个数一定是0，所以dp[0] = 0。

其他下标对应的数值呢？

考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j – coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

所以下标非0的元素都是应该是最大值。

4. 确定遍历顺序

本题并不强调是组合还是排列，所以两层for循环的顺序无所谓，内循环按照完全背包解法正序遍历即可。

需要注意的是，内循环中需要加入一个判断：if(dp[j - coins[i]] != Integer.MAX_VALUE)，这很重要！因为他可以排除如示例2所示的无法凑成相应背包容量的情况，具体可以用 coins = [2, 5] 推导一下，非常巧妙。

5. 举例推导dp数组

答案：

2.26：完全背包问题+求最小数-完全平方数

题目：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

• 输入：n = 12
• 输出：3
• 解释：12 = 4 + 4 + 4

示例 2：

• 输入：n = 13
• 输出：2
• 解释：13 = 4 + 9

分析：

把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品。

和上一题是一模一样的，只是书写代码时，在物品的设置上要有一些巧思，具体如何实现看下面代码即可。

答案：

2.27：拓展-多重背包问题

问题：

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

分析：

多重背包和01背包是非常像的， 为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少？

和如下情况没有区别：

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少？

和如下情况没有区别：

这就转成了一个01背包问题了，且每个物品只用一次。

代码：

int[] dp = new int[bagWeight + 1];

        //先遍历物品再遍历背包，作为01背包处理
        for (int i = 0; i < n; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                //遍历每种物品的个数
                for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }

3.1：动态规划-打家劫舍I

题目：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

• 示例 1：
• 输入：[1,2,3,1]
• 输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。

• 示例 2：
• 输入：[2,7,9,3,1]
• 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析：

看完题目后仔细想一想，当前房屋偷与不偷取决于前一个房屋和前两个房屋是否被偷了。

所以这里就更感觉到，当前状态和前面状态会有一种依赖关系，那么这种依赖关系都是动规的递推公式。

打家劫舍是dp解决的经典问题，接下来我们来动规五部曲分析如下：

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

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。（很重要，接下来的推导中一定要牢记）

2. 确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

• 如果偷第i房间，那么dp[i] = dp[i – 2] + nums[i] ，即第i-1房一定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
• 如果不偷第i房间，那么dp[i] = dp[i – 1]，说明递推公式认为按上一种方式偷到第i间房屋得到的金额比按另一种方式（也就是一路偷到i-1）偷到的少，因为dp[i – 1]也是一路递推过来的，所以最多可以偷窃的金额为dp[i – 1]。

然后dp[i]取最大值，即dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]);

3. dp数组如何初始化

从递推公式dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

4. 确定遍历顺序

dp[i] 是根据dp[i – 2] 和 dp[i – 1] 推导出来的，那么一定是从前到后遍历。

5. 举例推导dp数组

答案：

3.2：动态规划-打家劫舍II

题目：

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：

• 输入：nums = [2,3,2]

• 输出：3

• 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

• 输入：nums = [1,2,3,1]

• 输出：4

• 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

分析：

这道题之于上一题的进阶难点在于数组成环了。

其实本质上是多了一种限制：偷窃的房屋里不能同时包含首尾元素。

把这种约束融入到推导中，可以拆分为多个情况：

• 情况一：考虑不包含首尾元素。
• 情况二：考虑包含首元素，不包含尾元素。
• 情况三：考虑包含尾元素，不包含首元素。

注意这里用的是”考虑”，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素。

所以实际上情况二和情况三都包含了情况一，只需要考虑情况二和情况三就可以了。

分好情况后，剩下就和之前的没差别了，但是还是要留意一下代码的书写哦。

答案：

3.3：动态规划-打家劫舍III

题目：

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

分析：

对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

与之前的打家劫舍一样，关键是要讨论当前节点抢还是不抢。

如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）。

而动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。

这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

1. 确定递归函数的参数和返回值

这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

而该数组就是dp数组，其含义为：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

这样实际上就是用系统栈在递归的过程中帮我们保存每一层递归的参数。

2. 确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回{0,0}。

这也相当于dp数组的初始化。

3. 确定遍历顺序：后序遍历。

4. 确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，dp[1] = cur->val + left[0] + right[0]; 

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：dp[0] = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

5. 举例推导dp数组

答案：

3.4：动态规划-股票问题I

题目：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

• 示例 1：

• 输入：[7,1,5,3,6,4]

• 输出：5
  解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

• 示例 2：

• 输入：prices = [7,6,4,3,1]

• 输出：0
  解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

分析：

其实这道题完全可以贪心的，实际上贪心也要比动态规划快不少：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);  // 取最左最小价格
            result = max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
};

但是考虑到后面不断进阶的问题，我们还是要学习一下怎么使用动态规划：

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

dp[i][0] 表示第i天持有股票所得最多现金；

dp[i][1] 表示第i天不持有股票所得最多现金。

注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态。

2. 确定递推公式

• 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i – 1][0]
  • 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
• 那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i – 1][0], -prices[i]);
  
  
• 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i – 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i – 1][0]
• 同样dp[i][1]取最大的，dp[i][1] = max(dp[i – 1][1], prices[i] + dp[i – 1][0]);

3. dp数组如何初始化

显然，dp[0][0] -= prices[0]，dp[0][1] = 0。

4. 确定遍历顺序：从前往后。

5. 举例推导dp数组

dp[5][1]就是最终结果。

为什么不是dp[5][0]呢？

因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多。

答案：

3.5：动态规划-股票问题II

题目：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 示例 1:

• 输入: [7,1,5,3,6,4]

• 输出: 7
  解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

• 示例 2:

• 输入: [1,2,3,4,5]

• 输出: 4
  解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

• 示例 3:

• 输入: [7,6,4,3,1]

• 输出: 0
  解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

分析：

本题和前一题的唯一区别是本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）。

在动规五部曲中，这个区别主要是体现在递推公式上，其他都和上一题一样一样的。

在上一题中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格 即：dp[i – 1][1] – prices[i]。

这就是唯一的区别了。

答案：

3.6：动态规划-股票问题III

题目：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析：

关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

接来下我用动态规划五部曲详细分析一下：

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

一天一共就有五个状态：

0：没有操作 （其实我们也可以不设置这个状态）

1：第一次持有股票

2：第一次不持有股票

3：第二次持有股票

4：第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 – 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

2. 确定递推公式

达到dp[i][1]状态，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i][1] = – prices[i]（也可以写成dp[i-1][0] – prices[i]，实际上是一样的，只是和后面的写法统一）
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i – 1][1]

dp[i][1]一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] – prices[i], dp[i – 1][1]);

同理dp[i][2]也有两个操作：

• 操作一：第i天卖出股票了，那么dp[i][2] = dp[i – 1][1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i – 1][2]

所以dp[i][2] = max(dp[i – 1][1] + prices[i], dp[i – 1][2])

同理可推出剩下状态部分：

dp[i][3] = max(dp[i – 1][3], dp[i – 1][2] – prices[i]);

dp[i][4] = max(dp[i – 1][4], dp[i – 1][3] + prices[i]);

3. dp数组如何初始化

显然，dp[0][0] = 0，dp[0][1] = – prices[0]，dp[0][2] = 0，dp[0][3] = – prices[0]，dp[0][4] = 0。（其实就是在一天之内买了又卖，卖了又买）

4. 确定遍历顺序：从前往后。

5. 举例推导dp数组（这个例子不太好，正常来说3,4状态的值随着天数往后会大于1,2）

答案：

3.7：动态规划-股票问题IV

题目：

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 示例 1：

• 输入：k = 2, prices = [2,4,1]

• 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

• 示例 2：

• 输入：k = 2, prices = [3,2,6,5,0,3]

• 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

分析：

前几题的终极整合版，只是需要找个简单的规律，然后在初始化和递推代码的写法上有比较大的区别罢了。

1. 使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]

j的状态表示为：

• 0 表示不操作
• 1 第一次买入
• 2 第一次卖出
• 3 第二次买入
• 4 第二次卖出
• …..

应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。

题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。

2. 递推公式要做出一些改变：

for (int j = 0; j < 2 * k - 1; j += 2) {
  dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
  dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

3. 初始化：

for (int j = 1; j < 2 * k; j += 2) {
  dp[0][j] = -prices[0];
}

答案：

3.8：动态规划-股票问题含冷冻期

题目：

分析：

答案：