用一句话解释动态规划就是 “记住你之前做过的事”，如果更准确些，其实是 “记住你之前得到的答案”。

我举个大家工作中经常遇到的例子。

在软件开发中，大家经常会遇到一些系统配置的问题，配置不对，系统就会报错，这个时候一般都会去 Google 或者是查阅相关的文档，花了一定的时间将配置修改好。

过了一段时间，去到另一个系统，遇到类似的问题，这个时候已经记不清之前修改过的配置文件长什么样，这个时候有两种方案，一种方案还是去 Google 或者查阅文档，另一种方案是借鉴之前修改过的配置，第一种做法其实是万金油，因为你遇到的任何问题其实都可以去 Google，去查阅相关文件找答案，但是这会花费一定的时间，相比之下，第二种方案肯定会更加地节约时间，但是这个方案是有条件的，条件如下：

之前的问题和当前的问题有着关联性，换句话说，之前问题得到的答案可以帮助解决当前问题

需要记录之前问题的答案

当然在这个例子中，可以看到的是，上面这两个条件均满足，大可去到之前配置过的文件中，将配置拷贝过来，然后做些细微的调整即可解决当前问题，节约了大量的时间。

不知道你是否从这些描述中发现，对于一个动态规划问题，我们只需要从两个方面考虑，那就是找出问题之间的联系，以及记录答案，这里的难点其实是找出问题之间的联系，记录答案只是顺带的事情，利用一些简单的数据结构就可以做到。

思考动态规划问题的四个步骤

一般解决动态规划问题，分为四个步骤，分别是

问题拆解，找到问题之间的具体联系
状态定义
递推方程推导
实现

这里面的重点其实是前两个，如果前两个步骤顺利完成，后面的递推方程推导和代码实现会变得非常简单。

这里还是拿 Quora 上面的例子来讲解，“1+1+1+1+1+1+1+1” 得出答案是 8，那么如何快速计算 “1+ 1+1+1+1+1+1+1+1”，我们首先可以对这个大的问题进行拆解，这里我说的大问题是 9 个 1 相加，这个问题可以拆解成 1 + “8 个 1 相加的答案”，8 个 1 相加继续拆，可以拆解成 1 + “7 个 1 相加的答案”，… 1 + “0 个 1 相加的答案”，到这里，第一个步骤已经完成。

状态定义其实是需要思考在解决一个问题的时候我们做了什么事情，然后得出了什么样的答案，对于这个问题，当前问题的答案就是当前的状态，基于上面的问题拆解，你可以发现两个相邻的问题的联系其实是后一个问题的答案 = 前一个问题的答案 + 1，这里，状态的每次变化就是 +1。

定义好了状态，递推方程就变得非常简单，就是 dp[i] = dp[i - 1] + 1，这里的 dp[i] 记录的是当前问题的答案，也就是当前的状态，dp[i - 1] 记录的是之前相邻的问题的答案，也就是之前的状态，它们之间通过 +1 来实现状态的变更。

最后一步就是实现了，有了状态表示和递推方程，实现这一步上需要重点考虑的其实是初始化，就是用什么样的数据结构，根据问题的要求需要做那些初始值的设定。

public int dpExample(int n) {
    int[] dp = new int[n + 1];  // 多开一位用来存放 0 个 1 相加的结果
    dp[0] = 0;      // 0 个 1 相加等于 0
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
    }
    return dp[n];
}

你可以看到，动态规划这四个步骤其实是相互递进的，状态的定义离不开问题的拆解，递推方程的推导离不开状态的定义，最后的实现代码的核心其实就是递推方程，这中间如果有一个步骤卡壳了则会导致问题无法解决，当问题的复杂程度增加的时候，这里面的思维复杂程度会上升。

接下来我们再来看看 LeetCode 上面的几道题目，通过题目再来走一下这些个分析步骤。

题目实战

爬楼梯

但凡涉及到动态规划的题目都离不开一道例题：爬楼梯（LeetCode 第 70 号问题）。

题目描述

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

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

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

示例 1：

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

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

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

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

题目解析

爬楼梯，可以爬一步也可以爬两步，问有多少种不同的方式到达终点，我们按照上面提到的四个步骤进行分析：

问题拆解：
我们到达第 n 个楼梯可以从第 n - 1 个楼梯和第 n - 2 个楼梯到达，因此第 n 个问题可以拆解成第 n - 1 个问题和第 n - 2 个问题，第 n - 1 个问题和第 n - 2 个问题又可以继续往下拆，直到第 0 个问题，也就是第 0 个楼梯 (起点)

状态定义：
“问题拆解” 中已经提到了，第 n 个楼梯会和第 n - 1 和第 n - 2 个楼梯有关联，那么具体的联系是什么呢？你可以这样思考，第 n - 1 个问题里面的答案其实是从起点到达第 n - 1 个楼梯的路径总数，n - 2 同理，从第 n - 1 个楼梯可以到达第 n 个楼梯，从第 n - 2 也可以，并且路径没有重复，因此我们可以把第 i 个状态定义为 “从起点到达第 i 个楼梯的路径总数”，状态之间的联系其实是相加的关系。

递推方程：
“状态定义” 中我们已经定义好了状态，也知道第 i 个状态可以由第 i - 1 个状态和第 i - 2 个状态通过相加得到，因此递推方程就出来了 dp[i] = dp[i - 1] + dp[i - 2]

实现：
你其实可以从递推方程看到，我们需要有一个初始值来方便我们计算，起始位置不需要移动 dp[0] = 0，第 1 层楼梯只能从起始位置到达，因此 dp[1] = 1，第 2 层楼梯可以从起始位置和第 1 层楼梯到达，因此 dp[2] = 2，有了这些初始值，后面就可以通过这几个初始值进行递推得到。

参考代码

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }

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

三角形最小路径和

LeetCode 第 120 号问题：三角形最小路径和。

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

题目解析

给定一个三角形数组，需要求出从上到下的最小路径和，也和之前一样，按照四个步骤来分析：

问题拆解：
这里的总问题是求出最小的路径和，路径是这里的分析重点，路径是由一个个元素组成的，和之前爬楼梯那道题目类似，[i][j] 位置的元素，经过这个元素的路径肯定也会经过 [i - 1][j] 或者 [i - 1][j - 1]，因此经过一个元素的路径和可以通过这个元素上面的一个或者两个元素的路径和得到。

状态定义：
状态的定义一般会和问题需要求解的答案联系在一起，这里其实有两种方式，一种是考虑路径从上到下，另外一种是考虑路径从下到上，因为元素的值是不变的，所以路径的方向不同也不会影响最后求得的路径和，如果是从上到下，你会发现，在考虑下面元素的时候，起始元素的路径只会从[i - 1][j] 获得，每行当中的最后一个元素的路径只会从 [i - 1][j - 1] 获得，中间二者都可，这样不太好实现，因此这里考虑从下到上的方式，状态的定义就变成了 “最后一行元素到当前元素的最小路径和”，对于 [0][0] 这个元素来说，最后状态表示的就是我们的最终答案。

递推方程：
“状态定义” 中我们已经定义好了状态，递推方程就出来了

1	dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]

实现

这里初始化时，我们需要将最后一行的元素填入状态数组中，然后就是按照前面分析的策略，从下到上计算即可

参考代码

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();

    int[][] dp = new int[n][n];

    List<Integer> lastRow = triangle.get(n - 1);

    for (int i = 0; i < n; ++i) {
        dp[n - 1][i] = lastRow.get(i);
    }

    for (int i = n - 2; i >= 0; --i) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j < i + 1; ++j) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
        }
    }

    return dp[0][0];
}

最大子序和

LeetCode 第 53 号问题：最大子序和。

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

题目解析

求最大子数组和，非常经典的一道题目，这道题目有很多种不同的做法，而且很多算法思想都可以在这道题目上面体现出来，比如动态规划、贪心、分治，还有一些技巧性的东西，比如前缀和数组，这里还是使用动态规划的思想来解题，套路还是之前的四步骤：

问题拆解：
问题的核心是子数组，子数组可以看作是一段区间，因此可以由起始点和终止点确定一个子数组，两个点中，我们先确定一个点，然后去找另一个点，比如说，如果我们确定一个子数组的截止元素在 i 这个位置，这个时候我们需要思考的问题是 “以 i 结尾的所有子数组中，和最大的是多少？”，然后我们去试着拆解，这里其实只有两种情况：

这个位置的元素自成一个子数组;
i 位置的元素的值 + 以 i - 1 结尾的所有子数组中的子数组和最大的值

你可以看到，我们把第 i 个问题拆成了第 i - 1 个问题，之间的联系也变得清晰

状态定义

通过上面的分析，其实状态已经有了，dp[i] 就是 “以 i 结尾的所有子数组的最大值”

递推方程

拆解问题的时候也提到了，有两种情况，即当前元素自成一个子数组，另外可以考虑前一个状态的答案，于是就有了

1	dp[i] = Math.max(dp[i - 1] + array[i], array[i])

化简一下就成了：

1	dp[i] = Math.max(dp[i - 1], 0) + array[i]

实现

题目要求子数组不能为空，因此一开始需要初始化，也就是 dp[0] = array[0]，保证最后答案的可靠性，另外我们需要用一个变量记录最后的答案，因为子数组有可能以数组中任意一个元素结尾

参考代码

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;

    int[] dp = new int[n];

    dp[0] = nums[0];

    int result = dp[0];

    for (int i = 1; i < n; ++i) {
        dp[i] = Math.max(dp[i - 1], 0) + nums[i];
        result = Math.max(result, dp[i]);
    }

    return result;
}

上文解释了动态规划的一些基本特性和解题思路，也说了动态规划其实就是记住之前问题的答案，然后利用之前问题的答案来分析并解决当前问题，这里面有两个非常重要的步骤，就是拆解问题 和定义状态。

矩阵类动态规划问题

这次来针对具体的一类动态规划问题，矩阵类动态规划问题，来看看针对这一类问题的思路和注意点。

矩阵类动态规划，也可以叫做坐标类动态规划，一般这类问题都会给你一个矩阵，矩阵里面有着一些信息，然后你需要根据这些信息求解问题。

其实矩阵可以看作是图的一种，怎么说？你可以把整个矩阵当成一个图，矩阵里面的每个位置上的元素当成是图上的节点，然后每个节点的邻居就是其相邻的上下左右的位置，我们遍历矩阵其实就是遍历图，在遍历的过程中会有一些临时的状态，也就是子问题的答案，我们记录这些答案，从而推得我们最后想要的答案。

一般来说，在思考这类动态规划问题的时候，我们只需要思考当前位置的状态，然后试着去看当前位置和它邻居的递进关系，从而得出我们想要的递推方程，这一类动态规划问题，相对来说比较简单，我们通过几道例题来熟悉一下。

序列类动态规划问题

这次再来看一类动态规划问题，序列类动态规划问题，这类动态规划问题较为普遍，分析难度相比之前也略有提升，通常问题的输入参数会涉及数组或是字符串。

在开始之前，先解释一下子数组（子串）和子序列的区别，你可以看看下面这个例子：

输入数组：[1,2,3,4,5,6,7,8,9]
子数组：[2,3,4], [5,6,7], [6,7,8,9], …
子序列：[1,5,9], [2,3,6], [1,8,9], [7,8,9], …
可以看到的是，子数组必须是数组中的一个连续的区间，而子序列并没有这样一个要求。

你只需要保证子序列中的元素的顺序和原数组中元素的顺序一致即可，例如，在原数组中，元素 1 出现在元素 9 之前，那么在子序列中，如果这两个元素同时出现，那么 1 也必须在 9 之前。

为什么要说这个？

不知道你有没有发现，这里的子数组的问题和我们前面提到的矩阵类动态规划的分析思路很类似，只需要考虑当前位置，以及当前位置和相邻位置的关系。

通过这样的分析就可以把之前讲的内容和今天要介绍的内容关联起来了，相比矩阵类动态规划，序列类动态规划最大的不同在于，对于第 i 个位置的状态分析，它不仅仅需要考虑当前位置的状态，还需要考虑前面 i - 1 个位置的状态，这样的分析思路其实可以从子序列的性质中得出。

对于这类问题的问题拆解，有时并不是那么好发现问题与子问题之间的联系，但是通常来说思考的方向其实在于寻找当前状态和之前所有状态的关系，我们通过几个非常经典的动态规划问题来一起看看。

题目分析

最长上升子序列

LeetCode 第 300 号问题：最长上升子序列。

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

题目解析:
给定一个数组，求最长递增子序列。因为是子序列，这样对于每个位置的元素其实都存在两种可能，就是选和不选，如果我们用暴力的解法，枚举出所有的子序列，然后判断他们是不是递增的，选取最大的递增序列，这样做的话，时间复杂度是 O(2^n)，显然不高效。

那这里我们就需要思考用动态规划进行优化，我们按之前的四个步骤来具体分析一下：

问题拆解:
我们要求解的问题是 “数组中最长递增子序列”，一个子序列虽然不是连续的区间，但是它依然有起点和终点，比如：

[10,9,2,5,3,7,101,18]

子序列 [2,3,7,18] 的起始位置是 2，终止位置是 18
子序列 [5,7,101] 的起始位置是 5，终止位置是 101
如果我们确定终点位置，然后去看前面 i - 1 个位置中，哪一个位置可以和当前位置拼接在一起，这样就可以把第 i 个问题拆解成思考之前 i - 1 个问题，注意这里我们并不是不考虑起始位置，在遍历的过程中我们其实已经考虑过了。

状态定义:
问题拆解中我们提到 “第 i 个问题和前 i - 1 个问题有关”，也就是说 “如果我们要求解第 i 个问题的解，那么我们必须考虑前 i - 1 个问题的解”，我们定义 dp[i] 表示以位置 i 结尾的子序列的最大长度，也就是说 dp[i] 里面记录的答案保证了该答案表示的子序列以位置 i 结尾。

递推方程:
对于 i 这个位置，我们需要考虑前 i - 1 个位置，看看哪些位置可以拼在 i 位置之前，如果有多个位置可以拼在 i 之前，那么必须选最长的那个，这样一分析，递推方程就有了：

1	dp[i] = Math.max(dp[j],...,dp[k]) + 1,

其中 inputArray[j] < inputArray[i], inputArray[k] < inputArray[i]

实现:
在实现这里，我们需要考虑状态数组的初始化，因为对于每个位置，它本身其实就是一个序列，因此所有位置的状态都可以初始化为 1。

最后提一下，对于这道题来说，这种方法其实不是最优的，但是在这里的话就不展开讲了，理解序列类动态规划的解题思路是关键。

参考代码

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    // dp[i] -> the longest length sequence from 0 - i, and must include nums[i]
    int[] dp = new int[nums.length];

    Arrays.fill(dp, 1);

    int max = 0;

    for (int i = 0; i < nums.length; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }

        max = Math.max(max, dp[i]);
    }

    return max;
}

粉刷房子

LeetCode 第 256 号问题：粉刷房子。

注意：本题为 LeetCode 的付费题目，需要开通会员才能解锁查看与提交代码。

题目描述:

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。
例如，costs[0][0]表示第 0 号房子粉刷成红色的成本花费；costs[1][2]表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

题目解析

给 n 个房子刷油漆，有三种颜色的油漆可以刷，必须保证相邻房子的颜色不能相同，输入是一个 n x 3 的数组，表示每个房子使用每种油漆所需要花费的价钱，求刷完所有房子的最小价值。

还是按原来的思考方式走一遍：

问题拆解:
对于每个房子来说，都可以使用三种油漆当中的一种，如果说不需要保证相邻的房子的颜色必须不同，那么整个题目会变得非常简单，每个房子直接用最便宜的油漆刷就好了，但是加上这个限制条件，你会发现刷第 i 个房子的花费其实是和前面 i - 1 个房子的花费以及选择相关，如果说我们需要知道第 i 个房子使用第 k 种油漆的最小花费，那么你其实可以思考第 i - 1 个房子如果不用该油漆的最小花费，这个最小花费是考虑从 0 到当前位置所有的房子的。

状态定义:
通过之前的问题拆解步骤，状态可以定义成 dp[i][k]，表示如果第 i 个房子选择第 k 个颜色，那么从 0 到 i 个房子的最小花费

递推方程:
基于之前的状态定义，以及相邻的房子不能使用相同的油漆，那么递推方程可以表示成：

1	dp[i][k] = Math.min(dp[i - 1][l], ..., dp[i - 1][r]) + costs[i][k]， l != k, r != k

实现:
因为我们要考虑 i - 1 的情况，但是第 0 个房子并不存在 i - 1 的情况，因此我们可以把第 0 个房子的最小花费存在状态数组中，当然你也可以多开一格 dp 状态，其实都是一样的。

对于这道题目，你可能会问这不是和矩阵类动态规划类似吗？

如果单从房子来考虑的确是，但是对于颜色的话，我们必须考虑考虑相邻房子的所有颜色，这就有点序列的意思在里面了。

另外对于题目的分类其实没有严格的限定，主要是为了把相类似的问题放在一起，这样有便于分析问题思路。

参考代码

public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0) {
        return 0;
    }
    int n = costs.length;

    int[][] dp = new int[n][3];

    for (int i = 0; i < costs[0].length; ++i) {
        dp[0][i] = costs[0][i];
    }

    for (int i = 1; i < n; ++i) {
        dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
        dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
        dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
    }

    return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
}

粉刷房子II

LeetCode 第 265 号问题：粉刷房子II。

注意：本题为 LeetCode 的付费题目，需要开通会员才能解锁查看与提交代码。

题目描述

假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 
     或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5.

进阶：
您能否在 O(nk) 的时间复杂度下解决此问题？

题目解析

上面那道题目的 follow up，现在不是三种油漆，而是 k 种油漆。

其实解题思路还是不变。

对于第 i 个房子的每种颜色，我们对比看第 i - 1 个房子的 k 种油漆，找到不相重的最小值就好，但是这里的时间复杂度是 O(n*k^2)。

其实这是可以优化的，我们只需要在第 i - 1 个位置的状态中找到最大值和次大值，在选择第 i 个房子的颜色的时候，我们看当前颜色是不是和最大值的颜色相重，不是的话直接加上最大值，如果相重的话，我们就加上次大值，这样一来，我们把两个嵌套的循环，拆开成两个平行的循环，时间复杂度降至 O(n*k)。

参考代码(优化前)

public int minCostII(int[][] costs) {
    if (costs.length == 0 || costs[0].length == 0) {
        return 0;
    }

    int n = costs.length, k = costs[0].length;
    int[][] dp = new int[n][k];

    for (int i = 1; i < n; ++i) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }

    for (int i = 0; i < k; ++i) {
        dp[0][i] = costs[0][i];
    }        

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            for (int m = 0; m < k; ++m) {
                if (m != j) {
                    dp[i][m] = Math.min(dp[i][m], dp[i - 1][j] + costs[i][m]);
                }
            }
        }
    }

    int result = Integer.MAX_VALUE;
    for (int i = 0; i < k; ++i) {
        result = Math.min(result, dp[n - 1][i]);
    }

    return result;
}

参考代码(优化后)

public int minCostII(int[][] costs) {
    if (costs.length == 0 || costs[0].length == 0) {
        return 0;
    }

    int n = costs.length, k = costs[0].length;
    int[][] dp = new int[n][k];

    for (int i = 1; i < n; ++i) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }

    for (int i = 0; i < k; ++i) {
        dp[0][i] = costs[0][i];
    }

    for (int i = 1; i < n; ++i) {
        // min1 表示的是最大值，min2 表示的是次大值
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int l = 0; l < k; ++l) {
            if (min1 > dp[i - 1][l]) {
                min2 = min1;
                min1 = dp[i - 1][l];
                minIndex = l;
            } else if (min2 > dp[i - 1][l]) {
                min2 = dp[i - 1][l];
            }
        }

        for (int j = 0; j < k; ++j) {
            if (minIndex != j) {
                dp[i][j] = Math.min(dp[i][j], min1 + costs[i][j]);
            } else {
                dp[i][j] = Math.min(dp[i][j], min2 + costs[i][j]);
            }
        }
    }

    int result = Integer.MAX_VALUE;
    for (int i = 0; i < k; ++i) {
        result = Math.min(result, dp[n - 1][i]);
    }

    return result;
}

打家劫舍

LeetCode 第 198 号问题：打家劫舍。

题目描述

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

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

示例 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 。

题目解析

前面那道题目的 follow up，问的是如果这些房子的排列方式是一个圆圈，其余要求不变，问该如何处理。

房子排列方式是一个圆圈意味着之前的最后一个房子和第一个房子之间产生了联系，这里有一个小技巧就是我们线性考虑 [0, n - 2] 和 [1, n - 1]，然后求二者的最大值。

其实这么做的目的很明显，把第一个房子和最后一个房子分开来考虑。实现上面我们可以直接使用之前的实现代码。

这里有一个边界条件就是，当只有一个房子的时候，我们直接输出结果即可。

参考代码

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    if (nums.length == 1) {
        return nums[0];
    }

    int n = nums.length;

    return Math.max(
                    robI(Arrays.copyOfRange(nums, 0, n - 1)),
                    robI(Arrays.copyOfRange(nums, 1, n))
                   );
}

public int robI(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;

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

    dp[1] = nums[0];

    for (int i = 2; i <= n; ++i) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }

    return dp[n];
}

字符匹配类动态规划

字符匹配类动态规划，你一听名字就知道和字符串匹配相关，这类题型它其实是序列类动态规划的一个递进，它有时也被称为双序列类动态规划。

在序列类动态规划中，题目的输入是一个数组或是字符串，然后让你基于这个输入数组或是字符串进行一系列的判断，往往我们拆解问题、分析状态的时候只需要考虑一个维度的状态，比如刷房子和抢房子相关的问题，我们只需要考虑此时的房子和之前考虑过的房子之间的联系，思维始终是在一条线上。

回到字符匹配类动态规划，题目要你分析的是两个序列彼此之间的联系，这里其实有一个动态规划状态维度的提升，在考虑当前子问题的时候，我们要同时考虑两个序列的状态，当然，一般说来，动态规划状态维度的提升，也意味着难度的提升，可能刚从一维变成二维，你会不太习惯，没关系，多思考就好了，对于字符匹配类动态规划，它的题目特征其实特别明显，比如：

输入是两个字符串，问是否通过一定的规则相匹配
输入是两个字符串，问两个字符串是否存在包含被包含的关系
输入是两个字符串，问一个字符串怎样通过一定规则转换成另一个字符串
输入是两个字符串，问它们的共有部分
。。。
另外说一下，这类问题的难点在于问题的拆解上面，也就是如何找到当前问题和子问题的联系。

往往这类问题的状态比较好找，你可以先假设状态 dp[i][j] 就是子问题 str1(0…i) str2(0…j) 的状态。拆解问题主要思考 dp[i][j] 和子问题的状态 dp[i - 1][j]，dp[i - 1][j] 以及 dp[i - 1][j - 1] 的联系，因为字符串会存在空串的情况，所以动态规划状态数组往往会多开一格。

当然，对于这类问题，如果你还是没有什么思路或者想法，我给你的建议是画表格，我们结合实际题目一起来看看。

题目分析

LeetCode 第 1143 号问题：最长公共子序列。

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

1
2
3

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

1
2
3

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

1
2
3

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

题目分析

这里还是按之前的四个步骤来思考，当然这只是一个框架用来辅助你思考，不用特别拘泥于这四个步骤：

问题拆解:

我们要求解 str1(0,…m) 和 str2(0,…n) 的最长公共子序列，如果这是最终要求解的问题，那么它的子问题是什么呢？其实是 str1(0,…m-1) 和 str2(0,…n-1)，以及 str1(0,…m-1) 和 str2(0,…n)，还有 str1(0,…m) 和 str2(0,…n-1)，如果要找它们之间的关系，那我们需要思考一个问题就是，这些子问题怎么变成最终要求解的问题，当前的问题考虑当前字符是否相等，很直接的一个发现就是，如果 str1(m)==str2(n)，那么我们就可以将子问题中的 str1(0,…m-1) 和 str2(0,…n-1) 后面添加两个相同字符递进成当前问题；如果不相等，我们就需要考虑在三个子问题中选择一个较大值了。

说到这里，如果你还是不太清楚问题之间的联系，那我们一起来画画表格，熟悉一下这个过程：

题目求解 text1 = “abcde”, text2 = “ace” 的最长公共子序列

 ""  a  c  e
""  0  0  0  0
a   0             如果其中一个字符串是空串
b   0             那么两个字符不存在公共子序列
c   0             对应的子问题状态初始化为 0
d   0
e   0

 ""  a  c  e
""  0  0  0  0
a   0  1  1  1    text1 = "a"  text2 = "a" || text2 = "ac" || text2 = "ace"
b   0             考虑当前状态 dp[i][j] 的时候        
c   0             我们可以考虑子状态 dp[i - 1][j - 1]
d   0                             dp[i][j - 1]
e   0                             dp[i - 1][j]

 ""  a  c  e
""  0  0  0  0
a   0  1  1  1    
b   0  1  1  1    text1 = "ab"  text2 = "a" || text2 = "ac" || text2 = "ace"
c   0
d   0
e   0

 ""  a  c  e
""  0  0  0  0
a   0  1  1  1    
b   0  1  1  1
c   0  1  2  2    text1 = "abc"  text2 = "a" || text2 = "ac" || text2 = "ace"
d   0             画到这里，不知道你有没有发现当当前的字符不相同时
e   0                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

 ""  a  c  e
""  0  0  0  0
a   0  1  1  1    
b   0  1  1  1
c   0  1  2  2
d   0  1  2  2    text1 = "abcd"  text2 = "a" || text2 = "ac" || text2 = "ace"
e   0

 ""  a  c  e
""  0  0  0  0
a   0  1  1  1    
b   0  1  1  1
c   0  1  2  2
d   0  1  2  2    
e   0  1  2  3    text1 = "abcde"  text2 = "a" || text2 = "ac" || text2 = "ace"

3 就是我们要返回的答案
状态定义:
dp[i][j] 表示的就是 str1(0,…i) 和 str2(0,…j) 的答案，基本上字符串匹配类动态规划都可以先尝试这样去定义状态

递推方程:
在拆解问题中也说了，有两种情况，就是:

如果 str1(i) != str2(j):
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

如果 str1(i) == str2(j):
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)

因为 dp[i - 1][j - 1] + 1 >= dp[i - 1][j] && dp[i - 1][j - 1] + 1 >= dp[i][j - 1]
所以第二项可以化简：

如果 str1(i) == str2(j):
dp[i][j] = dp[i - 1][j - 1] + 1

实现
通常来说字符相关的问题可以把状态数组多开一格用来存放空串匹配的情况，这道题空串的情况答案都是 0，使用 Java 语言也不需要考虑初始化

参考代码

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[length1 + 1][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    for (int i = 1; i <= length1; ++i) {
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[length1][length2];
}

LeetCode 第 72 号问题：编辑距离。

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符
示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

题目分析

求解编辑距离，也是经典老题，编辑距离其实在实际工作中也会用到，主要用于分析两个单词的相似程度，两个单词的编辑距离越小证明两个单词的相似度越高。

题目说可以通过增加字符，删除字符，以及替换字符这三个操作来改变一个字符串，并且每个操作的 cost 都是 1，问一个单词转换成另一个单词的最小 cost，老样子，四个步骤分析一遍：

问题拆解:
我们考虑求解 str1(0…m) 通过多少 cost 变成 str2(0…n)，还是来看看它的子问题，其实还是三个

str1(0…m-1) 通过多少 cost 变成 str2(0…n)
str1(0…m) 通过多少 cost 变成 str2(0…n-1)
str1(0…m-1) 通过多少 cost 变成 str2(0…n-1)

一般字符匹配类问题的核心永远是两个字符串中的字符的比较，而且字符比较也只会有两种结果，那就是相等和不相等，在字符比较的结果之上我们才会进行动态规划的统计和推导。

回到这道题，当我们在比较 str1(m) 和 str2(n) 的时候也会有两种结果，即相等或不相等，如果说是相等，那其实我们就不需要考虑这两个字符，问题就直接变成了子问题 str1(0…m-1) 通过多少 cost 变成 str2(0…n-1)，如果说不相等，那我们就可以执行题目给定的三种变换策略:

将问题中的 str1 末尾字符 str1(m) 删除，因此只需要考虑子问题 str1(0…m-1)，str2(0…n)

将问题中的 str1 末尾字符 str1(m) 替换成 str2(n)，这里我们就只需要考虑子问题 str1(0…m-1)，str2(0…n-1)

将问题中的 str1 末尾添加一个字符 str2(n)，添加后 str1(m+1) 必定等于 str2(n)，所以，我们就只需要考虑子问题 str1(0…m)，str2(0…n-1)

如果你还不是特别清楚问题之间的关系，那就画图表吧，这里我就略过。

状态定义

dp[i][j] 表示的是子问题 str1(0…i)，str2(0…j) 的答案，和常规的字符匹配类动态规划题目一样，没什么特别

递推方程:
问题拆解那里其实说的比较清楚了，这里需要把之前的描述写成表达式的形式：

str1(i) == str2(j):
dp[i][j] = dp[i - 1][j - 1]
tip: 这里不需要考虑 dp[i - 1][j] 以及 dp[i][j - 1]，因为
   dp[i - 1][j - 1] <= dp[i - 1][j] +1 && dp[i - 1][j - 1] <= dp[i][j - 1] + 1

str1(i) != str2(j):
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][i - 1]) + 1

你可以看到字符之间比较的结果永远是递推的前提

实现:
这里有一个初始化，就是当一个字符串是空串的时候，转化只能通过添加元素或是删除元素来达成，那这里状态数组中存的值其实是和非空字符串的字符数量保持一致。

参考代码

public int minDistance(String word1, String word2) {
    char[] arr1 = word1.toCharArray();
    char[] arr2 = word2.toCharArray();

    int[][] dp = new int[arr1.length + 1][arr2.length + 1];
    dp[0][0] = 0;
    for (int i = 1; i <= arr1.length; ++i) {
        dp[i][0] = i;
    }

    for (int i = 1; i <= arr2.length; ++i) {
        dp[0][i] = i;
    }

    for (int i = 1; i <= arr1.length; ++i) {
        for (int j = 1; j <= arr2.length; ++j) {
            if (arr1[i - 1] == arr2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], 
                                    Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }
    }

    return dp[arr1.length][arr2.length];
}

LeetCode 第 44 号问题：通配符匹配。

题目描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ? 和 * 的通配符匹配。

? 可以匹配任何单个字符。
* 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输入: false

题目分析:
题目给定两个字符串，一个字符串是匹配串，除了小写字母外，匹配串里面还包含 * 和 ? 这两个特殊字符，另一个是普通字符串，里面只包含小写字母。

题目问这个普通字符串是否和匹配字符串相匹配，匹配规则是 ? 可以匹配单个字符，* 可以匹配一个区间，也就是多个字符，当然也可以匹配 0 个字符，也就是空串。

依然是四个步骤走一遍：

问题拆解:
做多了，你发现这种问题其实都是一个套路，老样子，我们还是根据我们要求解的问题去看和其直接相关的子问题，我们需要求解的问题是 pattern(0…m) 和 str(0…n) 是否匹配，这里的核心依然是字符之间的比较，但是和之前不同的是，这个比较不仅仅是看两个字符相不相等，它还有了一定的匹配规则在里面，那我们就依次枚举讨论下：

pattern(m) == str(n):
问题拆解成看子问题 pattern(0…m-1) 和 str(0…n-1) 是否匹配
pattern(m) == ?:
问题拆解成看子问题 pattern(0…m-1) 和 str(0…n-1) 是否匹配

你发现弄来弄去，子问题依然是那三个：
pattern(0…m-1) 和 str(0…n-1) 是否匹配
pattern(0…m-1) 和 str(0…n) 是否匹配
pattern(0…m) 和 str(0…n-1) 是否匹配

不知道你是否发现了字符匹配类动态规划问题的共性，如果是画表格，你只需要关注当前格子的左边、上边、左上这三个位置的相邻元素，因为表格有实际数据做辅助，所以画表格有时可以帮助你找到问题与子问题之间的联系。

状态定义:
还是老样子，dp[i][j] 表示的就是问题 pattern(0…i) 和 str(0…j) 的答案，直接说就是 pattern(0…i) 和 str(0…j) 是否匹配

递推方程:
把之前 “问题拆解” 中的文字描述转换成状态的表达式就是递推方程：

pattern(i) == str(j) || pattern(i) == '?':
dp[i][j] = dp[i - 1][j - 1]

pattern(i) == '*':
dp[i][j] = dp[i - 1][j] || dp[i][j - 1]

实现
这类问题的状态数组往往需要多开一格，主要是为了考虑空串的情况，这里我就不赘述了。

我想说的是，关于初始化的部分，如果 str 是空的，pattern 最前面有 *，因为 * 是可以匹配空串的，因此这个也需要记录一下，反过来，如果 pattern 是空的，str 只要不是空的就无法匹配，这里就不需要特别记录。

参考代码

public boolean isMatch(String s, String p) {
    char[] sArr = s.toCharArray();
    char[] pArr = p.toCharArray();

    boolean[][] dp = new boolean[pArr.length + 1][sArr.length + 1];

    dp[0][0] = true;
    for (int i = 1; i <= pArr.length; ++i) {
        if (pArr[i - 1] != '*') {
            break;
        } else {
            dp[i][0] = true;
        }
    }

    for (int i = 1; i <= pArr.length; ++i) {
        for (int j = 1; j <= sArr.length; ++j) {
            if (sArr[j - 1] == pArr[i - 1] || pArr[i - 1] == '?') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (pArr[i - 1] == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    }

    return dp[pArr.length][sArr.length];
}

LeetCode 第 97 号问题

题目描述

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

1 2	输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true

示例 2:

1 2	输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false

题目分析

题目的输入是三个字符串，问其中两个字符串是否能够交错合并组成第三个字符串，一个字符相对于其他字符的顺序在合并之后不能改变，这也是这道题的难点，不然的话你用一个哈希表就可以做了，三个字符串是否意味着要开三维的状态数组？还是四个步骤来看看：

问题拆解:
在拆解问题之前，我们必须保证前两个字符串的字符的总数量必须正好等于第三个字符串的字符总数量，不然的话，再怎么合并也无法完全等同。这里有一个点，当我们考虑 str1(0…i) 和 str2(0…j) 的时候，其实第三个字串需要考虑的范围也就确定了，就是 str3(0…i+j)。如果我们要求解问题 str1(0…m) 和 str2(0…n) 是否能够交错组成 str3(0…m+n)，还是之前那句话，字符串匹配问题的核心永远是字符之间的比较：

如果 str1(m) == str3(m+n)，问题拆解成考虑子问题 str1(0…m-1) 和 str2(0…n) 是否能够交错组成 str3(0…m+n-1)
如果 str2(n) == str3(m+n)，问题拆解成考虑子问题 str1(0…m) 和 str2(0…n-1) 是否能够交错组成 str3(0…m+n-1)

你可能会问需不需要考虑子问题 str1(0…m-1) 和 str2(0…n-1)？

在这道题目当中，不需要！

千万不要题目做多了就固定思维了，之前说到这类问题可以试着考虑三个相邻子问题是为了让你有个思路，能更好地切题，并不是说所有的字符串匹配问题都需要考虑这三个子问题，我们需要遇到具体问题具体分析。

状态定义:
dp[i][j] 表示的是 str1(0…i) 和 str2(0…j) 是否可以交错组成 str3(0…i+j)，这里再补充说明下为什么我们不需要开多一维状态来表示 str3，其实很简单，str3 的状态是由 str1 str2 决定的，str1 str2 定了，str3 就定了

递推方程:
把之前问题拆解中的文字描述转换成状态的表达式就是递推方程：

str1(i) == str3(i+j)
dp[i][j] |= dp[i - 1][j]

str2(j) == str3(i+j)
dp[i][j] |= dp[i - 1][j]

实现

初始化的时候需要考虑单个字符串能否组成 str3 对应的区间，这个比较简单，直接判断前缀是否相等即可。

参考代码：

public boolean isInterleave(String s1, String s2, String s3) {
    int length1 = s1.length();
    int length2 = s2.length();
    int length3 = s3.length();

    if (length1 + length2 != length3) {
        return false;
    }

    boolean[][] dp = new boolean[length1 + 1][length2 + 1];

    dp[0][0] = true;

    char[] sArr1 = s1.toCharArray();
    char[] sArr2 = s2.toCharArray();
    char[] sArr3 = s3.toCharArray();

    for (int i = 1; i <= length1; ++i) {
        dp[i][0] = dp[i - 1][0] && sArr1[i - 1] == sArr3[i - 1];
    }

    for (int i = 1; i <= length2; ++i) {
        dp[0][i] = dp[0][i - 1] && sArr2[i - 1] == sArr3[i - 1];
    }

    for (int i = 1; i <= length1; ++i) {
        for (int j = 1; j <= length2; ++j) {
            if (sArr3[i + j - 1] == sArr1[i - 1]) {
                dp[i][j] |= dp[i - 1][j];
            } 

            if (sArr3[i + j - 1] == sArr2[j - 1]) {
                dp[i][j] |= dp[i][j - 1];
            }
        }
    }

    return dp[length1][length2];
}

背包问题

概述

背包问题是一类比较特殊的动态规划问题，这篇文章的侧重点会在答案的推导过程上，我们还是会使用之前提到的解动态规划问题的四个步骤来思考这类问题。

在讲述背包问题之前，首先提及一下，背包类动态规划问题和其他的动态规划问题的不同之处在于，背包类动态规划问题会选用值来作为动态规划的状态，你可以回顾下之前我们讨论过的动态规划问题，基本上都是利用数组或者是字符串的下标来表示动态规划的状态。

针对背包类问题，我们依然可以画表格来辅助我们思考问题，但是背包类问题有基本的雏形，题目特征特别明显，当你理解了这类问题的解法后，遇到类似问题基本上不需要额外的辅助就可以给出大致的解法，这也就是说，学习背包类问题是一个性价比很高的事情，理解了一个特定问题的解法，基本上一类问题都可以直接套这个解法。

问题雏形

首先我们来看看这样一个问题：

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 C[i]，价值是 W[i]。求解将哪些物品装入背包可使价值总和最大。求出最大总价值

话不多说，我们还是按之前的分析四步骤来看看这个问题：

问题拆解:
我们要求解的问题是 “背包能装入物品的最大价值”，这个问题的结果受到两个因素的影响，就是背包的大小，以及物品的属性（包括大小和价值）。对于物品来说，只有两种结果，放入背包以及不放入背包，这里我们用一个例子来画画表格：

假设背包的大小是 10，有 4 个物品，体积分别是 [2,3,5,7]，价值分别是 [2,5,2,5]。

1、如果我们仅考虑将前一个物品放入背包，只要背包体积大于 2，此时都可以获得价值为 2 的最大价值：

图一

2、如果我们仅考虑将前两个物品放入背包，如果背包体积大于或等于 5，表示两个物体都可放入，此时都可以获得价值为 2+5=7 的最大价值，如果不能全都放入，那就要选择体积不超，价值最大的那个：

图二

3、如果我们仅考虑将前三个物品放入背包，如果背包体积大于或等于 10，表示三个物体都可放入，此时都可以获得价值为 2+5+2=9 的最大价值，如果不能全都放入，那就要选择体积不超，价值最大的那个方案：

图三
4、如果我们考虑将所有物品放入背包，我们可以依据前三个物品放入的结果来制定方案：

图四
这样，我们就根据物品和体积将问题拆分成子问题，也就是 “前 n 个物品在体积 V 处的最大价值” 可以由 “前 n - 1 个物品的情况” 推导得到。

状态定义:
在问题拆解中，我们得知问题其实和背包的体积还有当前考虑的物品有关，因此我们可以定义 dp[i][j] 表示 “考虑将前 i 个物品放入体积为 j 的背包里所获得的最大价值”

递推方程:
当我们考虑是否将第 i 个物品放入背包的时候，这里有两种情况

不放入，也就是不考虑第 i 个物品，那么问题就直接变成了上一个子问题，也就是考虑将 i - 1 个物品放入背包中，这样当前问题的解就是之前问题的解：

1	dp[i][j] = dp[i - 1][j]

如果背包体积大于第 i 个物品的体积，我们可以考虑将第 i 个物品放入，这个时候我们要和之前的状态做一个比较，选取最大的方案：

1	dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - C[i]] + W[i])

实现
实现这一环节还是主要考虑状态数组如何初始化，你可以看到，我们每次都要考虑 i - 1，另外还要考虑背包体积为 0 的情况，因此初始化数组时多开一格可以省去不必要的麻烦

public int zeroOnePack(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;

    // dp[i][j]: 对于下标为 0～i 的物品，背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];

    // 背包空的情况下，价值为 0
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不选物品 i 的话，当前价值就是取到前一个物品的最大价值，也就是 dp[i - 1][j]
            dp[i][j] = dp[i - 1][j];

            // 如果选择物品 i 使得当前价值相对不选更大，那就选取 i，更新当前最大价值
            if ((j >= C[i - 1]) && (dp[i][j] < dp[i - 1][j - C[i - 1]] + W[i - 1])) {
                dp[i][j] = dp[i - 1][j - C[i - 1]] + W[i - 1];
            }
        }
    }

    // 返回，对于所有物品（0～N），背包容量为 V 时的最大价值
    return dp[n][V];
}

这里还有一个空间上面的优化，如果你回到我们之前画的表格，考虑前 i 个问题的状态只会依赖于前 i - 1 个问题的状态，也就是 dp[i][…] 只会依赖于 dp[i - 1][…]，另外一点就是当前考虑的背包体积只会用到比其小的体积。

基于这些信息，我们状态数组的维度可以少开一维，但是遍历的方向上需要从后往前遍历，从而保证子问题需要用到的数据不被覆盖，优化版本如下：

public int zeroOnePackOpt(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;

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

    // 背包空的情况下，价值为 0
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= C[i]; --j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }

    return dp[V];
}

这里，因为物品只能被选中 1 次，或者被选中 0 次，因此我们称这种背包问题为 01 背包问题。

还有一类背包问题，物品可以被选多次或者 0 次，这类问题我们称为完全背包问题，这类背包问题和 01 背包问题很类似，略微的不同在于，在完全背包问题中，状态 dp[i][j] 依赖的是 dp[i - 1][j] 以及 dp[i][k] k < j，你可以看看下面的实现代码：

public int completePack(int V, int[] C, int[] W) {
    // 防止无效输入
    if (V == 0 || C.length != W.length) {
        return 0;
    }

    int n = C.length;

    // dp[i][j]: 对于下标为 0～i 的物品，背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];

    // 背包空的情况下，价值为 0
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不取该物品
            dp[i][j] = dp[i - 1][j];

            // 取该物品，但是是在考虑过或者取过该物品的基础之上(dp[i][...])取
            // 0-1背包则是在还没有考虑过该物品的基础之上(dp[i - 1][...])取
            if ((j >= C[i - 1]) && (dp[i][j - C[i - 1]] + W[i - 1] > dp[i][j])) {
                dp[i][j] = dp[i][j - C[i - 1]] + W[i - 1];
            }
        }
    }

    // 返回，对于所有物品（0～N），背包容量为 V 时的最大价值
    return dp[n][V];
}

类似的，我们还是可以对状态数组进行空间优化，依据我们之前讨论的状态之间的依赖关系，完全背包的空间优化我们直接把状态数组少开一维即可，遍历方式都不需要改变：

public int completePackOpt(int V, int[] C, int[] W) {
    if (V == 0 || C.length != W.length) {
        return 0;
    }

    int n = C.length;
    int[] dp = new int[V + 1];
    for (int i = 0; i < n; ++i) {
        for (int j = C[i]; j <= V; ++j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }

    return dp[V];
}

下面，我们就根据这两类背包问题，看看遇到类似的问题我们是否可以套用上面我们介绍的解法。

动态规划之背包问题系列

背包问题是一类经典的动态规划问题，它非常灵活，需要仔细琢磨体会，本文先对背包问题的几种常见类型作一个总结，再给出代码模板，然后再看看LeetCode上几个相关题目。

根据维基百科，背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：

01背包问题
完全背包问题
多重背包问题

此外，还存在一些其他考法，例如恰好装满、求方案总数、求所有的方案等。本文接下来就分别讨论一下这些问题。

01背包

题目

最基本的背包问题就是01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分析

如果采用暴力穷举的方式，每件物品都存在装入和不装入两种情况，所以总的时间复杂度是O(2^N)，这是不可接受的。而使用动态规划可以将复杂度降至O(NW)。我们的目标是书包内物品的总价值，而变量是物品和书包的限重，所以我们可定义状态dp:

dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W
那么我们可以将dp[0][0…W]初始化为0，表示将前0个物品（即没有物品）装入书包的最大价值为0。那么当 i > 0 时dp[i][j]有两种情况：

不装入第i件物品，即dp[i−1][j]；
装入第i件物品（前提是能装下），即dp[i−1][j−w[i]] + v[i]。

即状态转移方程为

1	dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
状态转移方程dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j]应该是value[0]，因为背包容量放足够放编号0物品。代码初始化如下：

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

那么问题来了，先遍历物品还是先遍历背包重量呢？其实都可以！！但是先遍历物品更好理解。那么我先给出先遍历物品，然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）例如这样：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = 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][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

由上述状态转移方程可知，dp[i][j]的值只与dp[i-1][0,...,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。需要注意的是，为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举（空间优化前没有这个限制），伪代码为：

// 01背包问题伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
    for j = W,...,w[i] // 必须逆向枚举!!!
        dp[j] = max(dp[j], dp[j−w[i]]+v[i])

时间复杂度为O(NW), 空间复杂度为O(W)。由于W的值是W的位数的幂，所以这个时间复杂度是伪多项式时间。

动态规划的核心思想避免重复计算在01背包问题中体现得淋漓尽致。第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定，暴力枚举忽略了这个事实。

完全背包

题目

完全背包（unbounded knapsack problem）与01背包不同就是每种物品可以有无限多个：一共有N种物品，每种物品有无限多个，第i（i从1开始）种物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分析一

我们的目标和变量和01背包没有区别，所以我们可定义与01背包问题几乎完全相同的状态dp:

dp[i][j]表示将前i种物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W
初始状态也是一样的，我们将dp[0][0…W]初始化为0，表示将前0种物品（即没有物品）装入书包的最大价值为0。那么当 i > 0 时dp[i][j]也有两种情况：

不装入第i种物品，即dp[i−1][j]，同01背包；
装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品。
所以状态转移方程为

1	dp[i][j] = max(dp[i−1][j], dp[i][j−w[i]]+v[i]) // j >= w[i]

这个状态转移方程与01背包问题唯一不同就是max第二项不是dp[i-1]而是dp[i]。

和01背包问题类似，也可进行空间优化，优化后不同点在于这里的 j 只能正向枚举而01背包只能逆向枚举，因为这里的max第二项是dp[i]而01背包是dp[i-1]，即这里就是需要覆盖而01背包需要避免覆盖。所以伪代码如下：

// 完全背包问题思路一伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
    for j = w[i],...,W // 必须正向枚举!!!
        dp[j] = max(dp[j], dp[j−w[i]]+v[i])

由上述伪代码看出，01背包和完全背包问题此解法的空间优化版解法唯一不同就是前者的 j 只能逆向枚举而后者的 j 只能正向枚举，这是由二者的状态转移方程决定的。此解法时间复杂度为O(NW), 空间复杂度为O(W)。

分析二

除了分析一的思路外，完全背包还有一种常见的思路，但是复杂度高一些。我们从装入第 i 种物品多少件出发，01背包只有两种情况即取0件和取1件，而这里是取0件、1件、2件…直到超过限重（k > j/w[i]），所以状态转移方程为：

1 2	// k为装入第i种物品的件数, k <= j/w[i] dp[i][j] = max{(dp[i-1][j − kw[i]] + kv[i]) for every k}

同理也可以进行空间优化，需要注意的是，这里max里面是dp[i-1]，和01背包一样，所以 j 必须逆向枚举，优化后伪代码为

// 完全背包问题思路二伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
    for j = W,...,w[i] // 必须逆向枚举!!!
        for k = [0, 1,..., j/w[i]]
            dp[j] = max(dp[j], dp[j−k*w[i]]+k*v[i])

相比于分析一，此种方法不是在O(1)时间求得dp[i][j]，所以总的时间复杂度就比分析一大些了，为 O(NWWw¯)级别。

分析三、转换成01背包

01背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为01背包问题来解：将一种物品转换成若干件只能装入0件或者1件的01背包中的物品。

最简单的想法是，考虑到第 i 种物品最多装入 W/w[i] 件，于是可以把第 i 种物品转化为 W/w[i] 件费用及价值均不变的物品，然后求解这个01背包问题。

更高效的转化方法是采用二进制的思想：把第 i 种物品拆成重量为 wi2k、价值为 vi2k 的若干件物品，其中 k 取遍满足 wi2k≤W 的非负整数。这是因为不管最优策略选几件第 i 种物品，总可以表示成若干个刚才这些物品的和（例：13 = 1 + 4 + 8）。这样就将转换后的物品数目降成了对数级别。具体代码见3.4节模板。

多重背包

题目

多重背包（bounded knapsack problem）与前面不同就是每种物品是有限个：一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

分析一

此时的分析和完全背包的分析二差不多，也是从装入第 i 种物品多少件出发：装入第i种物品0件、1件、…n[i]件（还要满足不超过限重）。所以状态方程为：

1 2	// k为装入第i种物品的件数, k <= min(n[i], j/w[i]) dp[i][j] = max{(dp[i-1][j − kw[i]] + kv[i]) for every k}

同理也可以进行空间优化，而且 j 也必须逆向枚举，优化后伪代码为

// 完全背包问题思路二伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
    for j = W,...,w[i] // 必须逆向枚举!!!
        for k = [0, 1,..., min(n[i], j/w[i])]
            dp[j] = max(dp[j], dp[j−k*w[i]]+k*v[i])

分析二、转换成01背包

采用2.4节类似的思路可以将多重背包转换成01背包问题，采用二进制思路将第 i 种物品分成了 O(logni) 件物品，将原问题转化为了复杂度为 O(W∑ilogni) 的 01 背包问题，相对于分析一是很大的改进，具体代码见3.4节。

代码模板

此节根据上面的讲解给出这三种背包问题的解题模板，方便解题使用。尤其注意其中二进制优化是如何实现的。

https://tangshusen.me/2019/11/24/knapsack-problem/
01背包, 完全背包, 多重背包模板(二进制优化). 
2020.01.04 by tangshusen.

用法:
    对每个物品调用对应的函数即可, 例如多重背包:
    for(int i = 0; i < N; i++) 
        multiple_pack_step(dp, w[i], v[i], num[i], W);

参数:
    dp   : 空间优化后的一维dp数组, 即dp[i]表示最大承重为i的书包的结果
    w    : 这个物品的重量
    v    : 这个物品的价值
    n    : 这个物品的个数
    max_w: 书包的最大承重
*/
void zero_one_pack_step(vector<int>&dp, int w, int v, int max_w){
    for(int j = max_w; j >= w; j--) // 反向枚举!!!
        dp[j] = max(dp[j], dp[j - w] + v);
}

void complete_pack_step(vector<int>&dp, int w, int v, int max_w){
    for(int j = w; j <= max_w; j++) // 正向枚举!!!
        dp[j] = max(dp[j], dp[j - w] + v);

    // 法二: 转换成01背包, 二进制优化
    // int n = max_w / w, k = 1;
    // while(n > 0){
    //     zero_one_pack_step(dp, w*k, v*k, max_w);
    //     n -= k;
    //     k = k*2 > n ? n : k*2;
    // }
}

void multiple_pack_step(vector<int>&dp, int w, int v, int n, int max_w){
   if(n >= max_w / w) complete_pack_step(dp, w, v, max_w);
   else{ // 转换成01背包, 二进制优化
       int k = 1;
       while(n > 0){
           zero_one_pack_step(dp, w*k, v*k, max_w);
           n -= k;
           k = k*2 > n ? n : k*2;
       }
   }
}

其他情形

恰好装满

背包问题有时候还有一个限制就是必须恰好装满背包，此时基本思路没有区别，只是在初始化的时候有所不同。

如果没有恰好装满背包的限制，我们将dp全部初始化成0就可以了。因为任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。如果有恰好装满的限制，那只应该将dp[0,…,N][0]初始为0，其它dp值均初始化为-inf，因为此时只有容量为0的背包可以在什么也不装情况下被“恰好装满”，其它容量的背包初始均没有合法的解，应该被初始化为-inf。

求方案总数

除了在给定每个物品的价值后求可得到的最大价值外，还有一类问题是问装满背包或将背包装至某一指定容量的方案总数。对于这类问题，需要将状态转移方程中的 max 改成 sum ，大体思路是不变的。例如若每件物品均是完全背包中的物品，转移方程即为

1	dp[i][j] = sum(dp[i−1][j], dp[i][j−w[i]]) // j >= w[i]

二维背包

前面讨论的背包容量都是一个量：重量。二维背包问题是指每个背包有两个限制条件（比如重量和体积限制），选择物品必须要满足这两个条件。此类问题的解法和一维背包问题不同就是dp数组要多开一维，其他和一维背包完全一样，例如5.4节。

求最优方案

一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由哪一个策略推出来的，这样便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。

以01背包为例，我们可以再用一个数组G[i][j]来记录方案，设 G[i][j] = 0表示计算 dp[i][j] 的值时是采用了max中的前一项(也即dp[i−1][j])，G[i][j] = 1 表示采用了方程的后一项。即分别表示了两种策略: 未装入第 i 个物品及装了第 i 个物品。其实我们也可以直接从求好的dp[i][j]反推方案：若 dp[i][j] = dp[i−1][j] 说明未选第i个物品，反之说明选了。

LeetCode相关题目

本节对LeetCode上面的背包问题进行讨论。

Partition Equal Subset Sum（分割等和子集）

Partition Equal Subset Sum（分割等和子集）

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

由于所有元素的和sum已知，所以两个子集的和都应该是sum/2（所以前提是sum不能是奇数），即题目转换成从这个数组里面选取一些元素使这些元素和为sum/2。如果我们将所有元素的值看做是物品的重量，每件物品价值都为1，所以这就是一个恰好装满的01背包问题。

我们定义空间优化后的状态数组dp，由于是恰好装满，所以应该将dp[0]初始化为0而将其他全部初始化为INT_MIN，然后按照类似1.2节的伪代码更新dp：

int capacity = sum / 2;
vector<int>dp(capacity + 1, INT_MIN);
dp[0] = 0;
for(int i = 1; i <= n; i++)
    for(int j = capacity; j >= nums[i-1]; j--)
        dp[j] = max(dp[j], 1 + dp[j - nums[i-1]]);

更新完毕后，如果dp[sum/2]大于0说明满足题意。

由于此题最后求的是能不能进行划分，所以dp的每个元素定义成bool型就可以了，然后将dp[0]初始为true其他初始化为false，而转移方程就应该是用或操作而不是max操作。完整代码如下：

bool canPartition(vector<int>& nums) {
    int sum = 0, n = nums.size();
    for(int &num: nums) sum += num;
    if(sum % 2) return false;
    
    int capacity = sum / 2;
    vector<bool>dp(capacity + 1, false);
    dp[0] = true;
    for(int i = 1; i <= n; i++)
        for(int j = capacity; j >= nums[i-1]; j--)
            dp[j] = dp[j] || dp[j - nums[i-1]];
        
    return dp[capacity];
}

另外此题还有一个更巧妙更快的解法，基本思路是用一个bisets来记录所有可能子集的和，详见我的Github。

Coin Change（零钱兑换）

Coin Change

题目给定一个价值amount和一些面值，假设每个面值的硬币数都是无限的，问我们最少能用几个硬币组成给定的价值。

如果我们将面值看作是物品，面值金额看成是物品的重量，每件物品的价值均为1，这样此题就是是一个恰好装满的完全背包问题了。不过这里不是求最多装入多少物品而是求最少，我们只需要将2.2节的转态转移方程中的max改成min即可，又由于是恰好装满，所以除了dp[0]，其他都应初始化为INT_MAX。完整代码如下：

int coinChange(vector<int>& coins, int amount) {
    vector<int>dp(amount + 1, INT_MAX);
    dp[0] = 0;
    
    for(int i = 1; i <= coins.size(); i++)
        for(int j = coins[i-1]; j <= amount; j++){
            // 下行代码会在 1+INT_MAX 时溢出
            // dp[j] = min(dp[j], 1 + dp[j - coins[i-1]]); 
            if(dp[j] - 1 > dp[j - coins[i-1]])
                dp[j] = 1 + dp[j - coins[i-1]];   
        }
    return dp[amount] == INT_MAX ? -1 : dp[amount];   
}

注意上面1 + dp[j - coins[i-1]]会存在溢出的风险，所以我们换了个写法。

另外此题还可以进行搜索所有可能然后保持一个全局的结果res，但是直接搜索会超时，所以需要进行精心剪枝，剪枝后可击败99%。详见我的Github。

Target Sum（目标和）

Target Sum

这道题给了我们一个数组（元素非负），和一个目标值，要求给数组中每个数字前添加正号或负号所组成的表达式结果与目标值S相等，求有多少种情况。

假设所有元素和为sum，所有添加正号的元素的和为A，所有添加负号的元素和为B，则有sum = A + B 且 S = A - B，解方程得A = (sum + S)/2。即题目转换成：从数组中选取一些元素使和恰好为(sum + S) / 2。可见这是一个恰好装满的01背包问题，要求所有方案数，将1.2节状态转移方程中的max改成求和即可。需要注意的是，虽然这里是恰好装满，但是dp初始值不应该是inf，因为这里求的不是总价值而是方案数，应该全部初始为0（除了dp[0]初始化为1）。所以代码如下：

int findTargetSumWays(vector<int>& nums, int S) {
    int sum = 0;
    // for(int &num: nums) sum += num;
    sum = accumulate(nums.begin(), nums.end(), 0);
    if(S > sum || sum < -S) return 0; // 肯定不行
    if((S + sum) & 1) return 0; // 奇数
    int target = (S + sum) >> 1;
    
    vector<int>dp(target + 1, 0);
    
    dp[0] = 1;
    for(int i = 1; i <= nums.size(); i++)
        for(int j = target; j >= nums[i-1]; j--)
            dp[j] = dp[j] + dp[j - nums[i-1]];
    
    return dp[target];
}

Ones and Zeros（一和零）

Ones and Zeroes

题目给定一个仅包含 0 和 1 字符串的数组。任务是从数组中选取尽可能多的字符串，使这些字符串包含的0和1的数目分别不超过m和n。

我们把每个字符串看做是一件物品，把字符串中0的数目和1的数目看做是两种“重量”，所以就变成了一个二维01背包问题，书包的两个限重分别是 m 和 n，要求书包能装下的物品的最大数目（也相当于价值最大，设每个物品价值为1）。

我们可以提前把每个字符串的两个“重量” w0和w1算出来用数组存放，但是注意到只需要用一次这两个值，所以我们只需在用到的时候计算w0和w1就行了，这样就不用额外的数组存放。完整代码如下：

int findMaxForm(vector<string>& strs, int m, int n) {
    int num = strs.size();
    int w0, w1;
    
    vector<vector<int>>dp(m+1, vector<int>(n+1, 0));
    
    for(int i = 1; i <= num; i++){
        w0 = 0; w1 = 0;
        // 计算第i-1个字符串的两个重量
        for(char &c: strs[i - 1]){
            if(c == '0') w0 += 1;
            else w1 += 1;
        }
        
        // 01背包, 逆向迭代更新dp
        for(int j = m; j >= w0; j--)
            for(int k = n; k >= w1; k--)
                dp[j][k] = max(dp[j][k], 1+dp[j-w0][k-w1]);
    }
    
    return dp[m][n];
}

总结

本文讨论了几类背包问题及LeetCode相关题目，其中01背包问题和完全背包问题是最常考的，另外还需要注意一些其他变种例如恰好装满、二维背包、求方案总数等等。除了本文讨论的这些背包问题之外，还存在一些其他的变种，但只要深刻领会本文所列的背包问题的思路和状态转移方程，遇到其它的变形问题，应该也不难想出算法。如果想更加详细地理解背包问题，推荐阅读经典的背包问题九讲。

空间优化 - 滚动数组

有一个比较通用的空间优化技巧没有在之前的文章中提到，很多的动态规划题目都可以套用这个技巧，我们就拿之前的最长公共子序列这道题目来举例说明，当时我们最终实现的代码是这样的：

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[length1 + 1][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    for (int i = 1; i <= length1; ++i) {
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[length1][length2];
}

你仔细观察代码，会发现当前考虑的状态 dp[i][j] 仅仅依赖于 dp[i - 1][j] 和 dp[i][j - 1]，如果画出表格，也就是当前行的格子只会和当前行以及前一行的格子有关，因此，保留两行数据就能够满足状态迭代更新的要求，我们可以得到下面的代码：

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[2][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    for (int i = 1; i <= length1; ++i) {
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[i%2][j] = dp[(i - 1)%2][j - 1] + 1;
            } else {
                dp[i%2][j] = Math.max(dp[(i - 1)%2][j], dp[i%2][j - 1]);
            }
        }
    }

    return dp[length1%2][length2];
}

这里我们成功将空间的维度降低了一维，当然如果你觉得取模的操作让代码变得不整洁，你也可以参考下面的代码：

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[2][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    int cur = 0, prev = 1;
    for (int i = 1; i <= length1; ++i) {
        prev = cur; cur = 1 - cur;
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[cur][j] = dp[prev][j - 1] + 1;
            } else {
                dp[cur][j] = Math.max(dp[prev][j], dp[cur][j - 1]);
            }
        }
    }

    return dp[cur][length2];
}

其实滚动数组的思想不难理解，就是只保存需要用到的子问题的答案（状态），覆盖那些不需要用到的子问题的答案，状态在同一块空间中不断翻滚迭代向前。

当然，有些动态规划的实现方式就不太容易使用这类优化，比如记忆化搜索，还有些动态规划题型，比如区间类动态规划，状态的更新不是逐行逐列的，使用滚动数组来优化也不是特别容易，因此使用滚动数组优化的时候还是需要结合实际情况考虑。

滚动数组一般来说都可以将状态数组的空间降低一维，比如三维变二维、二维变一维、一维变常数，当然有些具体题型的空间优化也可以做到这个，比如背包类型的动态规划问题中，我们通过改变遍历的顺序，直接就可以做到空间降维，但其实这是这类动态规划问题特有的优化，不属于滚动数组的范畴。

总结

动态规划系列内容算是结束了，虽然有关动态规划的知识点还有很多，但是我相信如果深刻掌握并理解了之前我们讲的内容，基本上 leetcode 上面 90% 以上的动态规划相关问题都可以很好解决。

当然了，要想达到熟能生巧的程度，还是需要多加练习，多思考，多对比，多总结，不然的话，学到的东西很快就会忘记。

最后的最后，希望动态规划不再是你面试中的拦路虎，看到它，也希望你能多一份亲切和自信。

思考动态规划问题的四个步骤

题目实战

爬楼梯

题目描述

题目解析

三角形最小路径和

题目描述

题目解析

实现

最大子序和

题目描述

题目解析

状态定义

递推方程

实现

矩阵类动态规划问题

相关题目解析

LeetCode 第 62 号问题：不同路径。

题目描述

题目解析

LeetCode 第 63 号问题：不同路径II

题目描述

题目解析

LeetCode 第 64 号问题：最小路径和

题目描述

题目解析

LeetCode 第 221 号问题：最大正方形。

题目描述

序列类动态规划问题

题目分析

最长上升子序列

粉刷房子

粉刷房子II

打家劫舍

相关的「股票」算法题

概念

使用场景

算法流程

实战练习

买卖股票的最佳时机

买卖股票的最佳时机 II

买卖股票的最佳时机 III

字符匹配类动态规划

题目分析

LeetCode 第 72 号问题：编辑距离。

LeetCode 第 44 号问题：通配符匹配。

LeetCode 第 97 号问题

背包问题

概述

问题雏形

相关题目实战

LeetCode 第 416 号问题：分割等和子集。

LeetCode 第 322 号问题：零钱兑换。

LeetCode 第 518 号问题：零钱兑换II。

K Sum。

动态规划之背包问题系列

01背包

题目

分析

完全背包

题目

分析一

分析二

分析三、转换成01背包

多重背包

题目

分析一

分析二、转换成01背包

代码模板

其他情形

恰好装满

求方案总数

二维背包

求最优方案

LeetCode相关题目

Partition Equal Subset Sum（分割等和子集）

Coin Change（零钱兑换）

Target Sum（目标和）

Ones and Zeros（一和零）

总结