08-动态规划
# 从斐波那契数列看动态规划
# 自上而下解决问题
斐波那契数列（Fibonacci Sequence），F(0)=1, F(1)=1, ..., F(n)=F(n-1)+F(n-2)，斐波那契数列是一个天然的递归表达式，可以很容易使用递归求出斐波那契数列第 n 项。
/**
* 递归求斐波那契数量第 n 项
*/
public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib1(n - 1) + fib1(n - 2);
}
2
3
4
5
6
7
8
根据斐波那契数列的定义得到这样的递归程序，但是其效率是非常慢的，因为其间有很多次重复的递归计算。下图为程序求 fib(5) 的递归树，其中内一个节点都是一次递归调用，可以看到其中有很多重复的递归调用，以 fib(3) 为例，在计算 fib(4) 的时候需要计算 fib(3)，在计算 fib(5) 的时候还要重新计算 fib(3)，每次都要递归到底。
有没有什么办法省略重复的递归算呢？可以使用记忆化搜索，记录下每次调用的结果，程序如下。
public int fib(int n) {
// 使用数组记录递归结果
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return memoryFib(n, memo);
}
/**
* 记忆化搜索求斐波那契数列
*/
private int memoryFib(int n, int[] memo) {
if (n == 0) return 0;
if (n == 1) return 1;
// 优先取数组中的结果，没有才进行递归
if (memo[n] == -1) {
memo[n] = memoryFib(n - 1, memo) + memoryFib(n - 2, memo);
}
return memo[n];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 自下而上解决问题
可以看到记忆化搜索的实质就是在递归的基础上加上记忆化的过程，递归是 自上而下 的解决为题，换句话说，我们没有从最基本的问题开始解决，而是假设最基本的问题已经解决了，即假设我们已经会求 fib(n-1) 和 fib(n-2) 了，我们就能求出 fib(n)，在此基础上加上递归终止条件，就完成了一个递归程序。对于这类问题，如果我们能自上而下的解决问题的话，那我们也能自下而上的解决问题，如下程序。
/**
* 动态规划求斐波那契数列
*/
public int fib3(int n) {
int[] memo = new int[n + 1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
}
2
3
4
5
6
7
8
9
10
11
12
可以看到这个代码的非常简单的，也很容易分析出其时间复杂度是 O(n) 级别，时间复杂度和记忆化搜索大致也是一个级别的（记忆化搜索 fib 方法会被调用 2n-1 次），且没有递归调用。这样动态规划数组中的每个元素只会被访问 1 次，而记忆化搜索中数组元素会被访问多次，所以动态规划效率更高。
这样的解法即 自下而上 的解决问题，先考虑小数据量下的这个问题的结果是怎样的，之后层层递归来解决更大数据量的结果是怎样的，通常这个过程就被称之为 动态规划。对于斐波那契数列问题使用动态规划很简单，但是更复杂的问题可能很难想到。
# 重叠子问题
以下是维基百科对于动态规划的定义：
动态规划常常适用于有
重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其
记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
为了更容易理解，可以参考下图。大多数动态规划问题，其本质都是一个递归问题，只不过在递归过程中，会发现所谓的 重叠子问题，对于重叠子问题我们怎么处理，我们可以使用记忆化搜索的方式来处理，记忆化搜索的方式是一种自顶向下的解决问题的方式，另外一种处理方式其实就是动态规划，动态规划的本质在我看来和记忆化搜索是一样的，只不过他是自底向上的解决问题。
在后续问题中，可以发现很多时候自定向上的解决问题是更容易的，有时候我们思考动态规划问题时会先自顶向下的思考问题，之后再用自底向上的方式实现。而事实上大多数时候记忆化搜索的方式都是能满足实际需求的，只不过使用动态规划的方式解决代码会更加简洁清晰。
# 第一个动态规划问题（爬楼梯）
# 问题分析
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
我们先自顶向下的思考问题的递归结构，我们爬到第 n 阶台阶的时候有两种可能，从 n-1 阶台阶再爬 1 阶，或者从 n-2 阶台阶再爬 2 阶。这样我们就把问题拆解成求爬上 n-1 阶和 n-2 阶台阶有多少种方法，两个结果相加就是爬上 n 阶台阶多有少种方法了。以此类推就形成了如下递归树，最后可以分解到求爬上 1 阶和 2 阶台阶分别有多少种方法，结果分别为climbStairs(1)=1，climbStairs(2)=2。
# 代码实现
经过以上分析，可以写出以下程序。
class Solution {
public int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}
}
2
3
4
5
6
7
可以发现这个代码和斐波那契数量非常相似。既然如此，自然能想到可以使用记忆化搜索的方式优化。
class Solution {
// 数组存放递归结果
private int[] memo;
public int climbStairs(int n) {
// 初始化数组
memo = new int[n + 1];
Arrays.fill(memo, -1);
return calcWays(n);
}
// 记忆化搜索方法
private int calcWays(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (memo[n] == -1) {
memo[n] = calcWays(n - 1) + calcWays(n - 2);
}
return memo[n];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
到这里我们应该可以进一步写出动态规划的解法。
/**
* 动态规划
* 时间复杂度: O(n)
* 空间复杂度: O(n)
*/
class Solution {
public int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int[] memo = new int[n + 1];
memo[1] = 1;
memo[2] = 2;
for (int i = 3; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
动态规划过程中我们发现，爬上 i 阶台阶的结果只依赖于爬上 i-1 和 i-2 的结果，所以没必要存储一个数组，只需要存储两个变量来记录前两个结果即可。
- 状态
F(x)：数列前 x 项 - 初始状态：
F(1) = 1，F(2) = 1 - 状态转移方程：
F(n) = F(n-1) + F(n-2)
/**
* 动态规划优化
* 时间复杂度: O(n)
* 空间复杂度: O(1)
*/
class Solution {
public int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int p = 1, q = 2;
for (int i = 3; i <= n; i++) {
q = p + q; // 结果
p = q - p; // 存原来的 q
}
return q;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 相关问题
120. 三角形最小路径和 (opens new window)中等
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
暴力递归（超时）
/** * 暴力递归 */ public class Solution1 { public int minimumTotal(List<List<Integer>> triangle) { return dfs(triangle, 0, 0); } /** * 计算点 (i, j) 到底边的最短路径，其中 i 表示自上而下第几层，j 表示第几个。 * 思路: 从点 (i, j) 到底边的最小路径，等于可达的下一层两个节点 (i+1, j) 和 (i+1, j+1) 到底边的最短路径中较小者，再加上本节点 */ private int dfs(List<List<Integer>> triangle, int i, int j) { if (i == triangle.size() - 1) return triangle.get(i).get(j); return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j); } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20记忆化搜索
/** * 记忆化搜索 * 时间复杂度: O(n^2) * 空间复杂度: O(n^2) */ public class Solution { // memo[i][j] 表示从第 i 行第 j 个元素走到底层的最小路径和 private Integer[][] memo; public int minimumTotal(List<List<Integer>> triangle) { memo = new Integer[triangle.size()][triangle.size()]; return dfs(triangle, 0, 0); } /** * 计算点 (i, j) 到底边的最短路径，其中 i 表示自上而下第几层，j 表示第几个。 * 思路: 从点 (i, j) 到底边的最小路径，等于可达的下一层两个节点 (i+1, j) 和 (i+1, j+1) 到底边的最短路径中较小者，再加上本节点 */ private int dfs(List<List<Integer>> triangle, int i, int j) { if (i == triangle.size() - 1) return triangle.get(i).get(j); if (memo[i][j] != null) return memo[i][j]; return memo[i][j] = triangle.get(i).get(j) + Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 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动态规划，自底向上递推
- 状态
F<i, j>：从第 i 层第 j 个点，<i, j>移动到底层的最小路径和 - 初始状态：最后一层到底层的最小路径和就是自身，
F<n-1, x> = V<n-1, x> - 状态转移方程：
F<i, j> = V<i, j> + Min(F<i+1, j>, F<i+1, j+1>)
/** * 动态规划，自底向上递推 * 时间复杂度: O(n^2) * 空间复杂度: O(n^2) */ public class Solution3 { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); // 总行数，也表示最后一层的节点数 // memo[i][j] 表示从点 (i, j) 到底层的最小路径和 int[][] memo = new int[n][n]; // 先填充最后一层所有节点到底层的最小路径和（就是自己） for (int j = 0; j < n; j++) memo[n - 1][j] = triangle.get(n - 1).get(j); // 倒数第二层开始，自底层向上层递推 for (int i = n - 2; i >= 0; i--) { for (int j = 0; j <= i; j++) { memo[i][j] = triangle.get(i).get(j) + Math.min(memo[i + 1][j], memo[i + 1][j + 1]); } } return memo[0][0]; } }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- 状态
动态规划，自顶向下递推
- 状态
F<i, j>：从顶点<0, 0>到第 i 层第 j 个点<i, j>的最小路径和 - 初始状态：
F<0, 0> = V<0, 0> - 状态转移方程：
F<i, j> = Min(F<i-1, j-1>, F<i-1, j>) + V<i, j>
不能直接得出结果，最后结果为最后一层所有的
F<n-1, x>的最小值。/** * 动态规划，自顶向下递推 * 时间复杂度: O(n^2) * 空间复杂度: O(n^2) */ public class Solution4 { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); // 总行数，也表示最后一层的节点数 // memo[i][j] 表示从顶点 (0, 0) 到点 (i, j) 的最小路径和 int[][] memo = new int[n][n]; memo[0][0] = triangle.get(0).get(0); // 从第 i = 1 层开始，自顶向下递推 for (int i = 1; i <= n - 1; i++) { for (int j = 0; j <= i; j++) { // (i, j) 只能从上一层 (i-1, j-1) 和 (i-1, j) 过来，取其中最小路径较小着加上自己。 // 同时注意上一层元素角标在 [0, i-1] 区间内，注意 j-1 和 j 不能越界 int topLeft = j - 1 < 0 ? Integer.MAX_VALUE : memo[i - 1][j - 1]; int topRight = j > i - 1 ? Integer.MAX_VALUE : memo[i - 1][j]; memo[i][j] = Math.min(topLeft, topRight) + triangle.get(i).get(j); } } // 遍历从顶层到最后一层所有节点的最小路径和，选出其中最小的 int res = memo[n - 1][0]; for (int j = 0; j < n; j++) res = Math.min(res, memo[n - 1][j]); return res; } }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- 状态
给定一个包含非负整数的
m * n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
# 发现重叠子问题和最优子结构（整数拆分）
# 问题分析
343. 整数拆分 (opens new window)中等
给定一个正整数 n，将其拆分为
至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
刚拿到这个问题的时候，我们可能没有头绪，当我们没有头绪的时候可以首先考虑如何暴力求解，用什么样的方案才能将对正整数 n 的所有分割方式都枚举出来呢？我们不知道要做几重循环，考虑使用递归的方式。事实上这个问题使用暴力解法是一个回溯的算法，复杂的是指数级的，记作 O(2^n)。
以分割 4 为例，分析这个问题的递归树如下。
借此可以推导出分割正整数 n 的递归树。
在分析出分割正整数的所有情况后，最后在所有情况里找到乘积的最大值就好了。和前面的例子一样，递归树中存在很多重叠子问题，这就提示我们可以使用记忆化搜索的方式来解决。
在这里介绍另一个概念：最优子结构。我们之所以可以使用这样的递归结构来解决这个问题是因为，求分割 n 获得的最大成绩，这是一个求最优化的问题，把它转化为求子问题的最优解，通过求子问题的最优解，可以获得原问题的最优解。这样的一个性质，叫做 最优子结构。
具体什么意思呢，我们再来看递归树，我们要想知道分割 n 获得的最大成绩，如果我们知道分割 n-1 的最大乘积、分割 n-2 的最大乘积……分割 1 获得的最大乘积，把这些答案综合起来，乘上线上的分割数字，我们就能知道分割 n 获得的最大乘积。换句话说，我们知道了子问题的最优解是多少，就能知道原问题的最优解是多少。
事实上也正是因为这个性质的存在，我们这棵递归树才得以存在，大家只要想清楚问题的递归结构，发现在这个递归结构中存在重叠子问题，其实我们就可以使用动态规划了。不过实际上严谨的来讲，看下图，对于一个递归问题，它应该同时满足重叠子问题和最优子结构这两个性质，这个情况这这个问题才能使用记忆化搜索和动态规划这两个方式来解决问题。
# 代码实现
下面我们具体编码解决这个整数分割的问题，一步步实现暴力求解、记忆化搜索和动态规划。
暴力求解
/** * 暴力递归 * 时间复杂度: O(n^n) * 空间复杂度: O(n) */ public class Solution { // 暴力递归解法 public int integerBreak(int n) { if (n == 1) return 1; int res = -1; // 记录最大乘积 // 这个循环表示每次都能将 n 分割成 i + (n-1) 的形式 for (int i = 1; i <= n - 1; i++) { // 比较结果，注意这里要比较三个，要加上只分割两个的情况 i*(n-1) res = max3(res, i * (n - i), i * integerBreak(n - i)); } return res; } // 辅助方法，求三个数的最大值 private int max3(int a, int b, int c) { return Math.max(a, Math.max(b, c)); } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23记忆化搜索
/** * 记忆化搜索 * 时间复杂度: O(n^2) * 空间复杂度: O(n) */ public class Solution { // 存储子结果 private int[] memo; public int integerBreak(int n) { memo = new int[n + 1]; memo[1] = 1; Arrays.fill(memo, -1); return integerBreakMemo(n); } // 记忆化搜索求解 public int integerBreakMemo(int n) { if (memo[n] != -1) return memo[n]; // 记录最大乘积 int res = -1; // 这个循环表示每次都能将 n 分割成 i + (n-1) 的形式 for (int i = 1; i <= n - 1; i++) { // 比较结果，注意这里要比较三个，要加上之分割两个的情况 i*(n-1) res = max3(res, i * (n - i), i * integerBreakMemo(n - i)); } memo[n] = res; return res; } // 辅助方法，求三个数的最大值 private int max3(int a, int b, int c) { return Math.max(a, Math.max(b, c)); } }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动态规划
- 状态：
F(x)表示拆分 x 得到的最大乘积 - 初始状态：
F(1) = 1 - 状态转移方程：
F(n) = Max{1*F(n-1), 2*F(n-2), ... , (n-1)*F(1)}
/** * 动态规划 * 时间复杂度: O(n^2) * 空间复杂度: O(n) */ public class Solution { // 动态规划求解 public int integerBreak(int n) { // 存储子结果 int[] memo = new int[n + 1]; memo[1] = 1; for (int i = 2; i <= n; i++) { // memo[2] -> memo[n] for (int j = 1; j <= i - 1; j++) { // 分出一段j: 1 -> i-1 // 这里需要对比三个数 // (1) 当前的 memo[i] // (2) 只分割成两个数 j * (i-j) // (3) 分割三个及以上 j * integerBreak(i-j) memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]); } } return memo[n]; } // 辅助方法，求三个数的最大值 private int max3(int a, int b, int c) { return Math.max(a, Math.max(b, c)); } }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- 状态：
# 相关问题
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1 'B' -> 2 ... 'Z' -> 261
2
3
4要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
- "AAJF" ，将消息分组为 (1 1 10 6)
- "KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
63. 不同路径 II (opens new window)
一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
# 状态的定义和状态转移（打家劫舍）
# 问题分析
198. 打家劫舍 (opens new window)中等
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
- 如 [3, 4, 1, 2]，则返回 6 [3, (4), 1, (2)]
- 如 [4, 3, 1, 2]，则返回 6 [(4), 3, 1, (2)]
暴力解法：检查所有房子的组合，对每一个组合，检查是否有相邻的房子，如果没有，记录其价值。找最大值。检查每种组合的复杂度是 O(n) 的，每个房子都有偷或不偷 2 种选择 ，共有 2^n 种组合，所示时间复杂的是 O((2^n)*n)。组合问题在之前介绍回溯的时候介绍过，忘记的不妨复习一下。这里的问题并不是让求所有的组合，而是让你求一个最大值，这是一个最优化问题，而它的解空间又是一个组合的解空间，我们很容易想到使用递归解决问题，那可以想一下会不会最终找到的递归结构中含有重叠子问题以及最优子结构这样的性质，进而我们就可以使用记忆化搜索以及动态规划来解决问题。
我们接下来分析一下，如果我们不是检查所有的组合，可以使用怎样的方法找到满足条件的不触发报警系统的情况。
对于 [0...n-1] 范围内的房子，我们先偷取的房子可以选择偷 0，1，...，n-1 号房子。假如我们最初偷取 0 号房子，那么接下来设立的子问题就是考虑偷取 [2...n-1] 号房子，因为必须跳过 1 号房子。以此类推，如果最初偷取 n-1 号房子，也就没有后续房子考虑了。按照上面的思路，可以继续分析递归树下一层的情况。
最后得到的递归树，很容易看到存在着重叠子问题，与此同时每一个问题其实都是在求解一个最优化的值，那么子问题最优化的值，配合当前的决策，在每一步中选择一个最大值，就能得到原问题的最优解。相当于它也最优子结构的性质，我们就可以使用记忆化搜索或者动态规划的方式解决问题。
对于这个问题，我们在进行进一步的形式化的分析。我们在之前的递归树中，每一个节点其实表达的是我们要解决一个问题，即 考虑 偷取 [x...n-1] 范围里的房子（函数的定义），我们每一个节点表示的要解决的问题在动态规划里通常称之为 状态，可以理解为递归函数中函数的定义。当我们完成了一个状态的定义之后，我们就要决定一个 状态的转移，即 状态转移方程：
f(0) = max { v(0)+f(2), v(1)+f(3), v(2)+f(4), ..., v(n-3)+f(n-1), v(n-2), v(n-1) }
设置一个函数 f(x)，定义即为考虑偷取 [x...n-1] 范围里的房子的最优解，即上文中函数的定义。那么整个问题是说考虑偷取 [0...n-1] 范围里的房子的收益为大致，就是求解 f(0)。为了获得最大收益，我们就要求方程中 max 大括号里的最大值，也就是递归树第二层的所有节点，这里 v(0) 表示偷取 0 号房子的收益，首次决定偷取 0 号房子后能获得的最大收益为 v(0)+f(2)，即 0 号房子收益加上 [2...n-1] 范围内的最大收益，和递归树第二层第一个节点对应。以此类推，首次决定偷取 i 号房子后，可以获得的最大收益为 v(i)+f(i+2)。直到最后的 n-2 和 n-1 号房子，最大收益就是 v(n-2) 和 v(n-1)。
至此，我们介绍了动态规划的 状态 和 状态转移，之后的动态规划问题也要搞清楚其中的状态是什么，状态转移的什么。下面开始编码实现本题。
# 代码实现
记忆化搜索
/** * 记忆化搜索 * 时间复杂度: O(n^2) * 空间复杂度: O(n) */ public class Solution { // memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益 private int[] memo; public int rob(int[] nums) { memo = new int[nums.length]; Arrays.fill(memo, -1); return rangeRob(nums, 0); } // 偷取 nums[index...nums.length) 范围的房子的最大收益 public int rangeRob(int[] nums, int index) { if (index >= nums.length) { return 0; } if (memo[index] != -1) { return memo[index]; } int res = 0; for (int i = index; i < nums.length; i++) { res = Math.max(res, nums[index] + rangeRob(nums, index + 2)); } memo[index] = res; return res; } }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动态规划
/** * 动态规划 * 时间复杂度: O(n^2) * 空间复杂度: O(n) */ public class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) { return 0; } // memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益 int[] memo = new int[n]; memo[n - 1] = nums[n - 1]; for (int i = n - 2; i >= 0; i--) { for (int j = i; j <= n - 1; j++) { memo[i] = Math.max(memo[i], nums[j] + (j + 2 >= n ? 0 : memo[j + 2])); } } return memo[0]; } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
动态规划问题需要明确状态的定义和状态的转移，本题我们对状态的定义是 考虑偷取 [x...n-1] 范围里的房子，并完成了代码实现。其实我们还可以将状态的定义设置为 考虑偷取 [0...x] 范围里的房子，大家可以思考这种定义下响应的逻辑变成了什么，即状态转移方程是什么，进一步思考如何代码实现。
暴力递归
/** * 暴力递归（超时） */ class Solution { public int rob(int[] nums) { return rob(nums, nums.length); } // 计算窃取 nums 中前 i 个房子获取的最大收益 private int rob(int[] nums, int i) { if (i == 0) return 0; if (i == 1) return nums[0]; return Math.max(rob(nums, i - 1), nums[i - 1] + rob(nums, i - 2)); } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15记忆化搜索
/** * 记忆化搜索 * 时间复杂度: O(n) * 空间复杂度: O(n) */ class Solution2 { // memo[i] 表示窃取前 i 个房子获得的最大收益 private int[] memo; public int rob(int[] nums) { memo = new int[nums.length + 1]; Arrays.fill(memo, -1); memo[0] = 0; // 前 0 个，一个不偷，收益 0 memo[1] = nums[0]; // 前 1 个，最大收益就是 nums[0] return rob(nums, nums.length); } // 计算窃取 nums 中前 i 个房子获取的最大收益 private int rob(int[] nums, int i) { if (memo[i] != -1) return memo[i]; int res = Math.max(rob(nums, i - 1), nums[i - 1] + rob(nums, i - 2)); memo[i] = res; return res; } }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动态规划
/** * 动态规划 * 时间复杂度: O(n) * 空间复杂度: O(n) */ class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) return 0; int[] memo = new int[n + 1]; // memo[i] 表示窃取前 i 个房子获得的最大收益 memo[0] = 0; // 前 0 个，一个不偷，收益 0 memo[1] = nums[0]; // 前 1 个，最大收益就是 nums[0] for (int i = 2; i <= n; i++) { memo[i] = Math.max(memo[i - 1], nums[i - 1] + memo[i - 2]); } return memo[n]; } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 相关问题
213. 打家劫舍 II (opens new window)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
337. 打家劫舍 III (opens new window)
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
309. 最佳买卖股票时机含冷冻期 (opens new window)
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
# 0-1 背包问题
# 问题分析
之前我们介绍了很多动态规划问题，对于这些问题我们找到其中的递归结构，发现其中的重叠子问题和最优子结构，进而转化为动态规划问题。下面我们介绍一个 0-1 背包问题，它不是 leetcode 上的标准问题，但是非常经典，可以帮助我们进一步理解动态规划的设计思路。
0-1 背包问题
有一个背包，它的容量为 C（Capacity），现在有 n 种不同的物品，编号为 0...n-1，其中每一件物品的重量为 w(i)，价值为 v(i)。问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大。
同样的我们可以首先思考如果使用暴力解法应该怎样做。对于这个问题也是在 n 种不同的物品种挑出有限的物品，令其满足一个容量的限制，同时总和最大。我们相当于还是要求这 n 个物品的组合。每一件物品我们都可以选择放进去或者不放进去 2 个选择，共有 2^n 种组合，面对每一种组合还需要求出总重是多少，那么暴力解法的时间复杂度是 O((2^n)*n)。这类组合问题我们都可以使用递归的方式来求解，只是过程种我们考虑是否有重叠子问题和最优子结构，进而转化为动态规划问题。
另外可能有同学会思考是不是可以使用贪心算法求解本题，即优先放入平均价值高的物品，其实这样是有问题的。比如有以下三样物品，每样重量为 weight，价值为 value，单位价值为 v/w，那么单位价值最高的是 0、1 号物品。如果我们有一个容量为 5 的背包，优先放入单位价值高的物品，只能放得下 [0,1]，价值为 16。但是如果放入 [1,2]，价值为 22。所以本题不适用贪心算法。
下面思考这个问题如何解决，考虑一个动态规划问题，首先要设立问题的状态，换言之，我们要设计一个递归函数，我们必须明确这个递归函数要完成什么事情，这里包括完成这个事情要哪些参数。之前我们介绍到的动态规划问题所设计的状态都是只用一个参数就解决了，通常我们问题种的参数的个数意味着我们要解决这个问题索要满足的约束条件。当前这个求最优解的背包问题有两个约束条件，分别为物品数量 n 和 背包容量 C，我们可以设立问题的状态为 F(n,C)，表示 考虑将 n 个物品放进容量为 C 的背包，使得价值最大。
明确了状态的定义后我们考虑如何设立这个状态的转移，这个状态的转移是这样的：
如果我们需要将 i 个物品放到容量为小 c 的背包中，我们可以有两种选择。
- 第 i 给物品不放入背包，此时问题的价值解为
F(i-1, c) - 第 i 给物品放入背包，此时背包容量变为
c-w(i)，此时价值最优解为v(i) + F(i-1, c-w(i))
这个任务面临的两种选择区别就是，对于第 i 个物品是否放入背包，然后在这两者之间选择一个最大值的策略。最后将这个过程整理一遍，就得到我们这个 0-1 背包问题的状态转移方程：
F(i, c) = max( F(i-1, c), v(i) + F(i-1, c-w(i)) )
得到了状态转移方程，我们下面来编码实现，先使用自顶向下的方式求解，大家可以看出这个状态转移方程正是自顶向下解决问题的思路，之后我们再把它改造为自底向上动态规划解决问题的思路。
# 代码实现
记忆化搜索
/** * 背包问题 * 记忆化搜索 * 时间复杂度: O(n*C) 其中 n 为物品个数; C 为背包容积 * 空间复杂度: O(n*C) */ public class Solution { // memo[i][c] 表示将 [0...i] 范围内的物品放入容量 c 的背包的最大价值 private int[][] memo; /** * 求解背包问题 * * @param w w[i] 表示第 i 号物品重量 * @param v v[i] 表示第 i 号物品价值 * @param C 背包容量 * @return 返回可放置的最大价值 */ public int knapsack(int[] w, int[] v, int C) { if (w == null || v == null || w.length != v.length || C < 0) { throw new IllegalArgumentException("Invalid param."); int n = w.length; if (n == 0 || C == 0) return 0; memo = new int[n][C + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j <= C; j++) { memo[i][j] = -1; } } return bestValue(w, v, w.length - 1, C); } /** * 考虑将 [0...index] 个物品放进容量为 c 的背包，使价值最大 * * @param w 物品重量 * @param v 物品价值 * @param index 考虑的物品范围 [0...index] * @param c 容量限制 * @return 返回可放置的最大价值 */ private int bestValue(int[] w, int[] v, int index, int c) { if (c <= 0 || index < 0) return 0; if (memo[index][c] != -1) return memo[index][c]; // 情况一：index 号物品不不放入 int res = bestValue(w, v, index - 1, c); if (c >= w[index]) { // 情况二：index 号物品放入 int otherRes = v[index] + bestValue(w, v, index - 1, c - w[index]); res = Math.max(res, otherRes); } return res; } }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
44
45
46
47
48
49
50
51
52
53
54
55
56
57动态规划
/** * 背包问题 * 动态规划 * 时间复杂度: O(n*C) 其中 n 为物品个数; C 为背包容积 * 空间复杂度: O(n*C) */ public class Solution { /** * 动态规划求解背包问题 * * @param w w[i] 表示第 i 号物品重量 * @param v v[i] 表示第 i 号物品价值 * @param C 背包容量 * @return 返回可放置的最大价值 */ public int knapsack(int[] w, int[] v, int C) { if (w == null || v == null || w.length != v.length || C < 0) throw new IllegalArgumentException("Invalid param."); int n = w.length; if (n == 0 || C == 0) return 0; // memo[i][c] 表示将 [0...i] 范围内的物品放入容量 c 的背包的最大价值 int[][] memo = new int[n][C + 1]; // 首先确定 [0...0] 范围内物品放入背包的最大价值，只要不超过背包容量，最大价值就是 v[0] for (int j = 0; j <= C; j++) { // 遍历任意容量，填充 v[0] 或 0 memo[0][j] = j >= w[0] ? v[0] : 0; } for (int i = 1; i < n; i++) { // 从第 i=1 号物品考虑，范围 [1...n-1] for (int j = 0; j <= C; j++) { // 从背包容量为 0 考虑，范围 [0...C] // 情况一：i 号物品不放入 memo[i][j] = memo[i - 1][j]; if (j >= w[i]) { // 情况二：i 号物品放入 int otherRes = v[i] + memo[i - 1][j - w[i]]; memo[i][j] = Math.max(memo[i][j], otherRes); // 取较大值 } } } return memo[n - 1][C]; } }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
44
45
# 0-1 背包问题的优化和变种
# 问题分析
上一节 0-1 背包问题的动态规划，时间复杂度 O(n*C)，空间复杂度 O(n*C)，本节我们考虑能否优化。从时间的角度已经很难优化了，但从空间的角度还有很大的优化空间。
首先看问题的状态和状态转移方程：
- 状态：考虑将 n 个物品放进容量为 C 的背包，使得价值最大
- 状态转移方程：
F(i, c) = max( F(i-1, c), v(i) + F(i-1, c-w(i)) )
对于状态转移方程可以发现，我们每次只更新一行的内容，而每次更新的内容依赖于 i-1 行的内容，而不考虑 i-1 行之前的元素是什么。换言之，我们只需要求出一行，就可以求出下一行，这一行之前的元素都可以丢弃。基于这样的思考，我们只需要保持两行元素就可以了，不需要保持 n 行元素，这种情况下算法的空间复杂度就变成了 O(2*C)，表示两行，每行都有 C 个元素，省略常数后空间复杂度为 O(c)。
如下图所示，首先处理使用第 0 行处理 i=0 的情况，然后基于第 1 行在第 0 行处理 i=1 的 情况。然后要开始处理 i=3 的情况，此时已经不需要 i=0 的数据了，所以用第 0 行处理 i=3 的情况。以此类推，两行交替处理，规律是第 0 行永远处理 i 等于偶数的情况，第 1 行永远处理 i 等于奇数的情况。那么编码实现的时候，我们遍历 i 的时候判断的使用哪一行参考哪一行时候，只需要判断 i 的奇偶就好了，即判断 i % 2。
# 代码实现
基于上面的分析，我们来优化 0-1 背包问题的动态规划实现。
/**
* 背包问题
* 动态规划，空间复杂度优化
* 时间复杂度: O(n*C) 其中 n 为物品个数; C 为背包容积
* 空间复杂度: O(C)
*/
public class Solution {
/**
* 动态规划解决背包问题，空间复杂度优化
*
* @param w w[i] 表示第 i 号物品重量
* @param v v[i] 表示第 i 号物品价值
* @param C 背包容量
* @return 返回可放置的最大价值
*/
public int knapsack(int[] w, int[] v, int C) {
if (w == null || v == null || w.length != v.length || C < 0)
throw new IllegalArgumentException("Invalid param.");
int n = w.length;
if (n == 0 || C == 0) return 0;
// 记录最大价值的空间优化版，一维索引为放入物品数量对 2 取模，二维索引为容量
// 后续设计 memo 数组的地方都要对 2 取模
int[][] memo = new int[2][C + 1];
// 首先确定 [0...0] 范围内物品放入背包的最大价值，只要不超过背包容量，最大价值就是 v[0]
for (int j = 0; j <= C; j++) { // 遍历任意容量，填充 v[0] 或 0
memo[0][j] = j >= w[0] ? v[0] : 0;
}
for (int i = 1; i < n; i++) { // 从第 i=1 号物品考虑，范围 [1...n-1]
for (int j = 0; j <= C; j++) { // 从背包容量为 0 考虑，范围 [0...C]
// 情况一：i 号物品不放入
memo[i % 2][j] = memo[(i - 1) % 2][j];
if (j >= w[i]) {
// 情况二：i 号物品放入
int otherRes = v[i] + memo[(i - 1) % 2][j - w[i]];
memo[i % 2][j] = Math.max(memo[i % 2][j], otherRes); // 取较大值
}
}
}
return memo[(n - 1) % 2][C];
}
}
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
44
45
46
我们使用这样的优化，将设计到 memo 二维数组的第一维索都对 2 取模，使得只需要保持两行元素就能解出 0-1 背包问题。我们有没有什么办法只是用一行大小为 C 的数组完成动态规划呢？
/**
* 背包问题
* 动态规划，空间复杂度优化 2
* 时间复杂度: O(n*C) 其中 n 为物品个数; C 为背包容积
* 空间复杂度: O(C), 只使用了 C 的额外空间
*/
public class Solution {
/**
* 动态规划解决背包问题，空间复杂度优化 2
*
* @param w w[i] 表示第 i 号物品重量
* @param v v[i] 表示第 i 号物品价值
* @param C 背包容量
* @return 返回可放置的最大价值
*/
public int knapsack(int[] w, int[] v, int C) {
if (w == null || v == null || w.length != v.length || C < 0)
throw new IllegalArgumentException("Invalid param.");
int n = w.length;
if (n == 0 || C == 0) return 0;
// 只使用一维数组，从右向左考虑
int[] memo = new int[C + 1];
// 首先确定 [0...0] 范围内物品放入背包的最大价值，只要不超过背包容量，最大价值就是 v[0]
for (int j = 0; j <= C; j++) { // 遍历任意容量，填充 v[0] 或 0
memo[j] = j >= w[0] ? v[0] : 0;
}
for (int i = 1; i < n; i++) { // 从第 i=1 号物品考虑，范围 [1...n-1]
for (int j = C; j >= w[i]; j--) { // 从背包容量为 C 反向考虑，范围 [w(i)...C]，小于 w(i) 时不用考虑了，因为放不下 i
// 取不放入 i 和放入 i，两者最大值
memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]); // memo[j - w[i]] 在上一轮已经求得
}
}
return memo[C];
}
}
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
# 相关问题
完全背包问题：每个物品可以无限使用。
多重背包问题：每个物品不止 1 个，有 num(i) 个。
多维费用背包问题：要考虑物品的体积和重量两个维度？
物品间加入更多约束。物品间可以互相排斥；也可以互相依赖。即如果放入物品 A，就不能（互斥）或者必须（依赖）放入物品 B。
# 面试中的 0-1 背包问题（分割等和子集）
# 问题分析
背包问题很多时候是不以背包的形态出现的，但是如果能看透其本质就是一个背包问题。
416. 分割等和子集 (opens new window)中等
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
- 如对 [1,5,11,5]，可以分割成 [1,5,5] 和 [11]，返回 true。
这个问题是一个非常典型的背包问题，在总重量为 sum 的 n 个物品中找出一定物品，填满 sum/2 容量的背包。其状态和状态转移方程如下。
- F(n, C) 考虑将 n 个物品填满容量为 C 的背包
F(i, c) = F(i-1, c) || F(i-1, c-w(i))，不放入i使用i-1的物品填满c；或者放入i，使用i-1的物品填满c-w(i)。 这两种方式有一种成功了，F(i, c)就成功了，因为c = sum[0,i] / 2，对于成功的 F(i, c) 有sum[0,i] - F(i,c) = sum[0,i] / 2。
下面开始编码实现。
# 代码实现
暴力递归
/** * <p> * 暴力递归 */ class Solution { public boolean canPartition(int[] nums) { // 计算 nums 总和，如果总和为奇数，肯定不能分割出等和子集 int sum = Arrays.stream(nums).sum(); if (sum % 2 == 1) return false; // 如果能从 nums 中找到总和为 sum/2 的子集，则满足题目要求 return tryPartition(nums, nums.length - 1, sum / 2); } /** * 尝试从 nums[0, idx] 中取出一个子集，使得组合总和为 sum， * 返回是否存在这样的组合 */ private boolean tryPartition(int[] nums, int idx, int sum) { if (idx < 0 || sum < 0) return false; if (sum == 0) return true; // ① nums[idx] 不放入，从 nums[0, idx-1] 中找出和为 sum 的子集 // ② nums[idx] 放入，从 nums[0, idx-1] 中找出和为 sum-nums[idx] 的子集 return tryPartition(nums, sum, idx - 1) || tryPartition(nums, sum - nums[idx], idx - 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记忆化搜索
/** * 记忆化搜索 * 时间复杂度: O(len(nums) * O(sum(nums))) * 空间复杂度: O(len(nums) * O(sum(nums))) */ class Solution { // memo[i][c] 表示使用索引为 [0...i] 的这些元素,是否可以完全填充一个容量为 c 的背包 // 0 表示为未计算; -1 表示不可以填充; 1 表示可以填充 private int[][] memo; public boolean canPartition(int[] nums) { // 计算总和 int sum = 0; for (int item : nums) sum += item; // 如果总和为奇数，一定不能分割出等和子集 if (sum % 2 == 1) return false; // 初始化记忆数组 memo = new int[nums.length][sum / 2 + 1]; return tryPartition(nums, nums.length - 1, sum / 2); } /** * 使用 nums[0...index], 是否可以完全填充一个容量为 sum 的背包 */ private boolean tryPartition(int[] nums, int index, int sum) { if (index < 0 || sum < 0) return false; if (sum == 0) return true; // 集合中找出和为 0 的子集可以满足 if (memo[index][sum] != 0) return memo[index][sum] == 1; // 计算过直接返回 // 递归计算是否满足，分 nums[index] 放入和不放入两种情况 boolean flag = tryPartition(nums, index - 1, sum) || tryPartition(nums, index - 1, sum - nums[index]); memo[index][sum] = flag ? 1 : -1; // 记忆化 return flag; } }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动态规划
- 状态：
F(i, t)表示能否从nums[0...i]中找出和为t的子集。 - 状态转移方程：
F(i, t) = F(i-1, t) || F(i-1, t-nums[i])，表示对于nums[i]可以选择不加入或加入子集中。 - 初始状态：
F(i, 0) = true；F(0, t)当且仅当t == 0或t == nums[0]时为 true。
/** * 动态规划 */ class Solution3 { public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) return false; int sum = 0; // 总和 int maxNum = 0; // 最大值 for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 != 0) return false; // 不是 2 的倍数，不能分为两个等和子集 int target = sum / 2; if (maxNum > target) return false; // 最大值大于总和一半，不能分为两个等和子集 // memo[i][t] 表示在 nums[0...i] 范围内能否找到和为 t 的子集（包含空集和全集） boolean[][] memo = new boolean[n][target + 1]; // 对于 memo[i][0]，只要取空集即可满足 for (int i = 0; i < n; i++) memo[i][0] = true; // 对于 memo[0][t]，只有一个数 nums[0]，只有 memo[0][0] 和 memo[0][nums[0]] 可以满足 memo[0][nums[0]] = true; // 对于 memo[i][t]，有子集包含 nums[i] 和不包含 nums[i] 两种情况 // 不包含: memo[i][t] = memo[i - 1][t] // 包含: memo[i][t] = memo[i - 1][t - nums[i]] for (int i = 1; i < n; i++) { for (int t = 1; t <= target; t++) { if (t >= nums[i]) memo[i][t] = memo[i - 1][t] || memo[i - 1][t - nums[i]]; else memo[i][t] = memo[i - 1][t]; } } return memo[n - 1][target]; } }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- 状态：
动态规划（优化）
/** * 动态规划 * 时间复杂度: O(len(nums) * O(sum(nums))) * 空间复杂度: O(len(nums) * O(sum(nums))) */ class Solution { public boolean canPartition(int[] nums) { int sum = 0; for (int item : nums) { sum += item; } // 总和为奇数，一定不能分割出等和子集 if (sum % 2 == 1) { return false; } int n = nums.length; // 物品数量 int capacity = sum / 2; // 背包容量 boolean[] memo = new boolean[capacity + 1]; // 记忆数组 // 首先考虑第 0 号元素是否能将背包填满 for (int j = 0; j <= capacity; j++) { // j 表示容量 memo[j] = (nums[0] == j); } // 从第 i=1 号物品考虑，范围 [1...n-1] for (int i = 1; i < n; i++) { // 从容量 capacity 反向考虑，范围 [nums(i)...C]，小于 nums(i) 时不用考虑了，因为放不下 i for (int j = capacity; j >= nums[i]; j--) { memo[j] = memo[j] || memo[j - nums[i]]; } } return memo[capacity]; } }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
# 相关问题
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
377. 组合总和 Ⅳ (opens new window)
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
# LIS 问题（最长递增子序列）
# 问题分析
300. 最长递增子序列 (opens new window)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
如：输入 [10,9,2,5,3,7,101,18]，其最长递增子序列是 [2,3,7,101]，因此输出长度为 4 。
还是老一套，如果没有思路先想想如何暴力求解，如果我们能找到所有的子序列，剩下的任务就是判断子序列是不是递增的，如果是就统计长度。那么如何找到所有的子序列呢，对于原数组种的每一个元素，都可以选择放进子序列或者不放进子序列中，有 n 个元素的话就有 2^n 种选择，时间复杂度是 O(2^n)，对于每一个子序列还要判断其是否是递增的，时间复杂度是 O(n)。所以对于暴力求解的时间复杂度是 O((2^n)*n)。
我们在此看到这是一个组合问题，这类问题肯定可以使用递归的方式来解决，关键就是能不能找到其中的重叠子问题和最优子结构，让其装换位记忆化搜索或动态规划问题。这里我们可以设置状态：
状态：LIS(i) 表示第 i 个数组为结尾的最长递增子序列的长度。
这样的表示似乎很难懂，可以这样说，LIS(i) 表示 [0...i] 范围呢，选择数字 nums[i] 可以获得的最长上升子序列的长度，注意其中的 nums[i] 必须被选取。
状态转移方程：
LIS(i) = max( 1 + LIS(j) if nums[i] > nums[j] )，其中j < i。什么意思呢？如果我们要求 LIS(i)，并且一定选择 nums[i]，我们要做的事情就是找 i 之前的所有的元素，如果发现某个 i 之前的元素满足 nums[j] < nums[i] 的话，我们又获得了一个新的上升子序列长度，其长度为
1 + LIS(j)，其中的 1 表示 nums[i]，LIS(j) 表示 [0...j] 范围内选取 j 元素获得的最大上升子序列，加起来就是 LIS(i)。
下面我们用题目中的测试用例 nums = [10,9,2,5,3,7,101,18]，模拟上述分析流程。
在初始化的时候每一个 LIS(i) 的值都为 1，表示每一个元素自身构成一个长度为 1 的上升子序列。然后我们就可以相到，当前面的最长上升子序列求出来后，后面的最长上升子序列也就能够求出来，所以我们从左往右考察元素。
nums 10 9 2 3 7 101 18 LIS 1 1 1 1 1 1 11
2对于 nums[0]=10 来说以 10 结尾的 LIS(0) 没得说就只有它自己，
LIS(0)=1；对于 nums[1]=9，前面是 {10}，凑不成上升序列，所以以 9 结尾的 LIS(1) 也只有它自己而已，
LIS(1)=1；对于 nums[2]=2，前面的 {10,9} 都大于 nums[2]，所以
LIS(2)=1；对于 nums[3]=5，可以和前面的 {nums[2]=2} 构成新的 LIS，nums[2] 对应的 LIS(2)=1，在加上 5 自己，所以
LIS(3) = 1+LIS(2) = 2；nums 10 9 2 3 7 101 18 LIS 1 1 2 1 1 1 11
2对于 nums[4]=3，可以跟在 {nums[2]=2} 后面组成新的 LIS，
LIS(4)= 1+LIS(2) = 2；nums 10 9 2 3 7 101 18 LIS 1 1 2 2 1 1 11
2对于 nums[5]=7，可以跟在 {nums[2]=2, nums[3]=5, nums[4]=3} 后面组成新的 LIS，其中 LIS(3)=LIS(4)=2 最长，所以
LIS(5) = 1+LIS(3) = 1+LIS(4) = 3；nums 10 9 2 3 7 101 18 LIS 1 1 2 2 3 1 11
2对于 nums[6]=101，可以跟在 {nums[0]=10, nums[1]=9, nums[2]=2, nums[3]=5, nums[4]=3, nums[5]=7} 后面组成新的 LIS，其中 LIS(5)=3 最长，所以
LIS(6) = 1+LIS(5) = 4nums 10 9 2 3 7 101 18 LIS 1 1 2 2 3 4 11
2对于 nums[6]=101，可以跟在 {nums[0]=10, nums[1]=9, nums[2]=2, nums[3]=5, nums[4]=3, nums[5]=7} 后面组成新的 LIS，其中 LIS(5)=3 最长，所以
LIS(6) = 1+LIS(5) = 4nums 10 9 2 3 7 101 18 LIS 1 1 2 2 3 4 41
2
注意：当考察到 num[i] 的时候，必须逐个和前面的元素对比看是否能组成上升子序列，而不是说从后往前找，找到的第一个比 nums[i] 小的元素 j，然后就得到 LIS(i) = 1 + LIS(j)，这是不成立的。很容易通过下面一个反例解释：
nums 10 15 20 11 9 101
LIS 1 2 3 2 1 4
2
这个例子中 nums = [10,15,20,11,9,101]，对于 nums[5]=101 来说，LIS(5)= 1+LIS(2) = 4，而不是 1+LIS(4) = 2。
至此，这个最长上升子序列的算法过程已经描述清除了，下面开始编码实现。
# 代码实现
通过之前的分析，这个问题已经是一个非常标准的递推的过程了，就是从最小的问题逐步求解更大的问题，可以直接使用动态规划解决了。感兴趣可以继续使用递归加上记忆化搜索实现。
动态规划
/** * 动态规划 * 时间复杂度: O(n^2) * 空间复杂度: O(n) */ public class Solution { public int lengthOfLIS(int[] nums) { // memo[i] 表示以 nums[i] 结尾的最长上升子序列的长度，初始为 1，表示只包含自己 int[] memo = new int[nums.length]; Arrays.fill(memo, 1); // 逐个考察以 nums[i] 结尾的最长上升子序列 for (int i = 1; i < nums.length; i++) { // 逐个考察 nums[i] 前面的元素是否能和 nums[i] 构成上升序列 for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { memo[i] = Math.max(memo[i], 1 + memo[j]); } } } // 选出最长的 int res = memo[0]; for (int item : memo) { res = Math.max(res, item); } return res; } }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记忆化搜索
/** * 记忆化搜索 * 时间复杂度: O(n^2) * 空间复杂度: O(n) */ public class LongestIncreasingSubsequence2 { // memo[i] 表示以 nums[i] 结尾的最长递增子序列的长度 private int[] memo; public int lengthOfLIS(int[] nums) { memo = new int[nums.length]; Arrays.fill(memo, -1); int res = 1; // 逐个考察以 nums[i] 结尾的最长递增子序列的长度 for (int i = 0; i < nums.length; i++) { res = Math.max(res, getMaxLength(nums, i)); } return res; } /** * 以 nums[index] 为结尾的最长上升子序列的长度 */ private int getMaxLength(int[] nums, int index) { if (memo[index] != -1) { return memo[index]; } int res = 1; // 逐个考察 index 之前的元素是否能和 nums[index] 组成新的递增子序列 for (int i = 0; i < index; i++) { if (nums[i] < nums[index]) { res = Math.max(res, 1 + getMaxLength(nums, i)); } } memo[index] = res; return res; } }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
本节使用动态规划解决 LIS 问题，时间复杂度是 O(n^2)，还存在一种 O(nlogn) 的解法，不过不是使用动态规划的解法了，又兴趣的可以搜索自学一下这种解法。
# 相关问题
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
- 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
# 更多动态规划问题
# LCS 问题（最长公共子序列）
最长公共子序列 Longest Common Sequence (LCS)
给出两个字符串S1和S2，求这两个字符串的最长公共子序列的长度。
例一：输出 13
- S1 = AAACCGTGAGTTATTCGTTCTAGAA
- S2 = CACCCCTAAGGTACCTTTGGTTC
例二：输出 3
- S1 = ABCD
- S2 = AEBD
这个问题又是一个典型的需要有两个维度进行动态规划的问题，因为我们需要在两个字符串中进行扫描。状态设置如下。
状态：
LCS(m, n)表示字符串 S1[0...m] 范围和字符串 S2[0...n] 范围的最长公共子序列的长度。根据这个状态定义，其实每次关键比较的就是 S1[m] 和 S2[n] 这两个关键字符，考虑这两个字符的时候有两种情况：
S1[m] == S2[n]：两个字符相等，则LCS(m, n) = 1 + LCS(m-1, n-1)S1[m] != S2[n]：两个字符不相等，则LCS(m, n) = max( LCS(m-1, n), LCS(m, n-1) )
状态转移方程：上面的两种情况就是此问题的状态转移方程
上面的分析可能还是很抽象，下面根据具体的例子分析。对于 S1="ABCD" 和 S2="AEBD" 这两个字符串，来分析求最长公共子序列的过程。
# dijkstra 单源最短路径算法
其实图论中 dijkstra 单源最短路径算法也是动态规划，其状态定义如下：
状态：
shortestPath(i)，表示从 start 到 i 的最短路径长度状态转移方程：``shortestPath(i) = min( shortPath(a) + w(a->i) )`
其中 a 是直接指向 i 的节点，
w(a->i)表示 a 到 i 的距离，所以求 shortPath(i) 就转换为，对于所有的指向 i 的节点 a，从 start 到 a 的最短路径再加上 a 到 i 的距离，即min( shortPath(a) + w(a->i) )。
有兴趣可以自己使用以上动态规划的思想写出单源最短路径算法，再和标准的 dijkstra 算法实现比较，加深动态规划和最短路径算法的理解。