爬楼梯、零钱兑换问题题解 - 递归、回溯循序渐进理解动态规划

爬楼梯问题

为了和后面讲解的 零钱兑换 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
// 注意这个写法是“傻”递归,可以增加 memo 减少递归次数。
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) {
// dp[i] = dp[i] + 0;
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 11 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);
// 辅助队列,记录下一次取 coin 的 index
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] < 0d[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];
// 初始化最基础的case
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 解题的关键还是要能够识别出状态,和写出状态转移方程,我们可以通过一些具体的例子,再范化为抽象的状态转移方程,有了方程再翻译成为代码就太轻松了。