爬楼梯问题
为了和后面讲解的 零钱兑换 II 问题做对比，我这里把原本的 爬楼梯 问题修改一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬台阶的个数可在 int[] steps 数组中选择。你有多少种不同的方法可以爬到楼顶呢？
注意：n 是一个正整数，steps 数组中的数字也正整数。
例子：
输入： n = 5, steps = [1,2,5]
输出： 9
走法：
1. 1 1 1 1 1
2. 1 1 1 2
3. 1 1 2 1
4. 1 2 1 1
5. 1 2 2
6. 2 1 1 1
7. 2 1 2
8. 2 2 1
9. 5
|
递归
先找到相同子问题，以上面例子为例，我们要走到第 5 层，只有可能是从第 4 层上来，或从第 3 层上了，或者从第 0 层上来，因为只能爬 1、2、5 步。这时候问题就转换成：到第 4 层台阶有几种 + 到第 3 层台阶有几种 + 到第 0 层台阶有几种。递归树是：
递归的方式解决:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int climbStairs(int n, int[] steps) {
int res = 0;
if (n == 0) {
return 1;
}
if (n < 0) {
return 0;
}
for (int step : steps) {
res = res + climbStairs(n - step, steps);
}
return res;
}
|
BFS
有了递归状态树，我们不难写出 BFS 的代码，这个不是我们今天研究的重点，为了解题方式的完整性，我这里顺便提一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int climbStairs(int n, int[] steps) {
int res = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(n);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Integer count = queue.poll();
for (int step : steps) {
int newCount = count - step;
if (newCount == 0) {
res ++;
} else if (newCount > 0) {
queue.add(newCount);
}
}
}
}
return res;
}
|
回溯（DFS）
假如每次都走数组第一个元素对应的步数，按照题目例子：我们每次都选择走一步一共走 5 步正好到达楼顶，就是 1 1 1 1 1 这种情况。这时候我们回溯第 5 步，不选择数组第一个元素 ‘1’，因为已经选过了，而是选第二个元素 ‘2’ ，发现超出了楼梯总数，所以不能选择，同理第三个元素也是。此时第 5 步的情况都已经考虑，我们回溯到第 4 步，同样不选择数组第一个元素 ‘1’，而是选第二个元素 ‘2’，正好到达楼顶就是 1 1 1 2 这种情况，依此类推直到回溯到第一个元素为 ‘5’ 的情况。
上面的解释过程就其实就是 DFS 遍历过程，我把代码放在下面，大家可以运行一下看看打印出的结果就一目了然了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int climbStairs(int n, int[] steps) {
return dfs(steps, n, new ArrayList<>());
}
private int dfs(int[] steps, int n, List<Integer> path) {
if (n == 0) {
System.out.println("方法: " + path);
return 1;
}
if (n < 0) {
return 0;
}
int res = 0;
for (int i = 0; i < steps.length; i++) {
path.add(steps[i]);
res += dfs(steps, n - steps[i], path);
path.remove(path.size() - 1);
}
return res;
}
|
动态规划
回顾一下递归法和回溯法我们思考问题的方式。
递归法关键是找到重复子问题，问题和子问题，除了处理的数据规模不同，解决思路完全相同。这是一种 自顶向下 的解决过程，我们想解决 f(5) 问题，就要先解决 f(4)、f(3)、f(0) 问题，它们就是数据规模不同。当规模小到极致时， 即 f(0) 是已经知解，就是递归终止条件。
回溯就是采用试错的思想，穷举所有的解，找到满足要求的解。在有岔路的地方，先都选第一个路口，一条路走到黑，再回溯到上个步骤，选择第二个路口，直到回溯所有情况。这个穷举的过程是具有重复性的，所以回溯的问题通常也用递归代码实现。回溯是一个有规律、不会重复、不会遗漏的穷举方法。
在讲 DP 之前我先想一下，现在有 1 层台阶有 1 种走法，有 2 层台阶有 2 种走法，如果是 N 层呢？
DP 实际是一个 自底向上 的过程，我们通过 2 个最简单的情况，可以向上推出复杂的情况。用 DP 中的概念就是后面阶段的状态可以通过前面阶段的状态推导出来。这个例子中的 DP 状态 就是台阶数量，因为原问题和子问题中变化量只有台阶数量，这样可以得到状态转移方程：
1
2
3
| 0, n < 0
dp(n) = 1, n == 0
sum(dp[i - step]), step 属于 steps
|
如下是 DP 解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int climbStairs(int n, int[] steps) {
int[] dp = new int[n + 1];
dp[0] = 1;
for(int i = 1; i <= n; i++) {
for (int step : steps) {
if (i < step) {
continue;
} else {
dp[i] = dp[i] + dp[i - step];
}
}
}
return dp[n];
}
|
零钱兑换问题
爬楼梯问题是个引子，因为它的状态很简单，你可能没有感觉，现在我们再看看 零钱兑换 II 问题：
1
2
3
4
5
6
7
8
9
10
| 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
例子：
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=5
|
这个问题乍一看，貌似和上面的爬楼梯问题一摸一样，但为什么少了很多种解 ？是因为爬楼梯问题中，相同的组合不同的排列认为是不同的解，比方说 2 1 1 1 和 1 1 1 2 在爬楼梯问题中是两个解，但是零钱兑换中只能认为是一个解，也就是说零钱兑换问题，只能接受不同组合的解。排除相同解的思路很简单，我们拿硬币的时候，每次只能拿上一次一样位置的硬币，或者后面的硬币，比如我们第一次拿了 coins 数组第二个位置的面值 2 ， 下一次只能拿第二个位置的 2 ，或三个位置的 5 ， 而不能拿第一个位置的 1 。
所以我们用递归、BFS、回溯（DFS）、动态规划解题的时候，我们需要多记录一个状态，就是下一次开始拿硬币的索引。
递归
我们先用递归方式解决试试，只需要在递归方程中加入下一次拿硬币的索引 start 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int change(int amount, int[] coins) {
return helper(coins, 0, amount);
}
private int helper(int[] coins, int start, int amount) {
if (amount == 0) {
return 1;
}
if (amount < 0) {
return 0;
}
int result = 0;
for (int i = start; i < coins.length; ++i) {
result += helper(coins, i, amount - coins[i]);
}
return result;
}
|
BFS
为了解题方式的完整性，同样我用 BFS 方法解答一下。为了避免重复结果，同样需要我们记录下一次广度遍历拿硬币的索引。如下的例子我用的是一个辅助队列，记录下一次遍历时取硬币的索引：
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
| public int change(int amount, int[] coins) {
int res = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(amount);
Queue<Integer> coinStart = new LinkedList<>();
coinStart.add(0);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Integer count = queue.poll();
Integer idx = coinStart.poll();
for (int j = idx; j < coins.length; j++) {
int newCount = count - coins[j];
if (newCount == 0) {
res ++;
} else if (newCount > 0) {
queue.add(newCount);
coinStart.add(j);
}
}
}
}
return res;
}
|
回溯（DFS）
回溯也是同样的套路，我就不再赘述了，同学们可以和爬楼梯的问题对比着看。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int coinChange(int[] coins, int amount) {
int res = dfs(coins, amount, 0, new ArrayList<>());
return res == 0 ? -1 : res;
}
private int dfs(int[] coins, int amount, int level, List<Integer> path) {
if (amount == 0) {
System.out.println("方法: " + path);
return 1;
}
if (amount < 0) {
return 0;
}
int res = 0;
for (int i = level; i < coins.length; i++) {
path.add(coins[i]);
res += dfs(coins, amount - coins[i], i, path);
path.remove(path.size() - 1);
}
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
58
59
60
61
| 原问题是 coins = [1,2,5], amount = 5, 有多少种方法，我们先将规模减小思考一下：
0. 逐步增大集合规模，凑 0 元
coins = [1], amount = 0
0 = 1 * 0 表示：0个1元
coins = [1,2], amount = 0
0 = 1 * 0 + 2 * 0 表示：0个1元，0个2元
coins = [1,2,5], amount = 0
0 = 1 * 0 + 2 * 0 + 5 * 0 表示：0个1元，0个2元，0个5元
1. 逐步增大集合规模，凑 1 元
coins = [1], amount = 1
1 = 1 * 1 表示：1个1元
coins = [1,2], amount = 1
1 = 1 * 1 + 2 * 0 表示：1个1元，0个2元
coins = [1,2,5], amount = 1
1 = 1 * 1 + 2 * 0 + 5 * 0 表示：1个1元，0个2元，0个5元
2. 逐步增大集合规模，凑 2 元
coins = [1], amount = 2
2 = 1 * 2 表示：2个1元
coins = [1,2], amount = 2
2 = 1 * 2 + 2 * 0 表示：2个1元，0个2元
2 = 1 * 0 + 2 * 1 表示：0个1元，1个2元
coins = [1,2,5], amount = 2
2 = 1 * 2 + 2 * 0 + 5 * 0 表示：2个1元，0个2元，0个5元
2 = 0 * 2 + 2 * 1 + 5 * 0 表示：0个1元，1个2元，0个5元
3. 逐步增大集合规模，凑 3 元
coins = [1], amount = 3
3 = 1 * 3 表示：3个1元
coins = [1,2], amount = 3
3 = 1 * 3 + 2 * 0 表示：3个1元，0个2元
3 = 1 * 1 + 2 * 1 表示：1个1元，1个2元
coins = [1,2,5], amount = 3
3 = 1 * 3 + 2 * 0 + 5 * 0 表示：3个1元，0个2元，0个5元
3 = 1 * 1 + 2 * 1 + 5 * 0 表示：1个1元，1个2元，0个5元
4. 逐步增大集合规模，凑 4 元
coins = [1], amount = 4
4 = 1 * 4 表示：4个1元
coins = [1,2], amount = 4
4 = 1 * 4 + 2 * 0 表示：4个1元，0个2元
4 = 1 * 2 + 2 * 1 表示：2个1元，1个2元
4 = 1 * 0 + 2 * 2 表示：0个1元，2个2元
coins = [1,2,5], amount = 4
4 = 1 * 4 + 2 * 0 + 5 * 0 表示：4个1元，0个2元，0个5元
4 = 1 * 2 + 2 * 1 + 5 * 0 表示：2个1元，1个2元，0个5元
4 = 1 * 0 + 2 * 2 + 5 * 0 表示：0个1元，2个2元，0个5元
5. 逐步增大集合规模，凑 5 元
coins = [1], amount = 5
5 = 1 * 5 表示：5个1元
coins = [1,2], amount = 5
5 = 1 * 5 + 2 * 0 表示：5个1元，0个2元
5 = 1 * 3 + 2 * 1 表示：3个1元，1个2元
5 = 1 * 1 + 2 * 2 表示：1个1元，2个2元
coins = [1,2,5], amount = 5
5 = 1 * 5 + 2 * 0 + 5 * 0 表示：5个1元，0个2元，0个5元
5 = 1 * 3 + 2 * 1 + 5 * 0 表示：3个1元，1个2元，0个5元
5 = 1 * 1 + 2 * 2 + 5 * 0 表示：1个1元，2个2元，0个5元
5 = 1 * 0 + 2 * 0 + 5 * 1 表示：0个1元，0个2元，1个5元
|
我们把上面穷举精简成为表格可以看的清晰一些：
|
d[0,1] = 0 |
d[0,2] = 0 |
d[0,3] = 0 |
d[0,4] = 0 |
d[0,5] = 0 |
| d[1,0] = 1 |
d[1,1] = 1 |
d[1,2] = 1 |
d[1,3] = 1 |
d[1,4] = 1 |
d[1,5] = 1 |
| d[2,0] = 1 |
d[2,1] = 1 |
d[2,2] = 2 |
d[2,3] = 2 |
d[2,4] = 3 |
d[1,5] = 3 |
| d[3,0] = 1 |
d[3,1] = 1 |
d[3,2] = 2 |
d[3,3] = 2 |
d[3,4] = 3 |
d[3,5] = 4 |
表格里 DP 状态定义为 d[i, j] ，表示用 [0, i - 1] 的面值硬币的集合，凑成目标值为 j 的组合数量。 状态定义中包含了硬币面值集合来避免产生重复结果。
状态转移方程： d[i, j] = d[i -1, j] + d[i, j - coins[i - 1]] ，
d[i - 1, j] 表示不使用第 i - 1 个的面值来凑 j ，即使用第 [0, i - 2] 的面值的硬币来凑 j
d[i, j - coins[i - 1]] 表示，使用了第 i - 1 个的面值来凑 j ，所以凑 j 的时候要把 coins[i - 1] 的面额减去。如果 j - coins[i - 1] < 0 则 d[i, j - coins[i - 1]] = 0。
举个例子：
1
2
3
4
5
6
| d[1,1] = d[0,1] + d[1,0] = 0 + 1 = 1
d[1,2] = d[0,2] + d[1,1] = 0 + 1 = 1
d[1,3] = d[0,3] + d[1,2] = 0 + 1 = 1
d[2,3] = d[1,3] + d[2,1] = 1 + 1 = 2
d[2,5] = d[1,5] + d[2,3] = 1 + 2 = 3
d[3,5] = d[2,5] + d[3,0] = 3 + 1 = 4
|
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int change(int amount, int[] coins) {
int[][] d = new int[coins.length + 1][amount + 1];
for (int i = 0; i < d.length; i++) {
d[i][0] = 1;
}
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
int tmp = j - coins[i - 1];
if (tmp >= 0) {
d[i][j] = d[i - 1][j] + d[i][tmp];
} else {
d[i][j] = d[i - 1][j];
}
}
}
return d[coins.length][amount];
}
|
用 DP 解题的关键还是要能够识别出状态，和写出状态转移方程，我们可以通过一些具体的例子，再范化为抽象的状态转移方程，有了方程再翻译成为代码就太轻松了。
