0%

排序算法

如何评价一种排序算法

既然是算法,肯定要分析时间复杂度、空间复杂度。关于时间复杂度是指比较和交换次数,关于空间复杂度是指排序算法申请的额外空间,原地排序就是特指空间复杂度是 O(1) 的排序算法。 另外排序算法还涉及稳定性的评价指标,是指对于比较结果相同的数据,如果每次排序数据顺序都是一样的,那么则是稳定的排序算法,反之则是不稳定的排序算法。

冒泡排序(Bubble Sort)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void bubbleSort(int[] nums) {
int length = nums.length;
if (length <= 1) {
return;
}
for (int i = 0; i < length; i++) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = length - 1; j > i; j--) {
if (nums[j] > nums[j - 1]) { // 交换
int tmp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) {
break; // 没有数据交换,提前退出
}
}
}

插入排序(Insertion Sort)

插入排序的算法思想就是,将数组中的数据分已排序区间和未排序区间。初始状态就是数组的第一个元素为已排序区间,右边为未排序区间。依次从未排序区间中取出元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void insertionSort(int[] nums) {
int length = nums.length;
if (length <= 1) {
return;
}
for (int i = 1; i < length; i++) {
int value = nums[i];
int j = i - 1;
// 查找插入的位置
while (j >= 0) {
if (nums[j] > value) {
nums[j + 1] = nums[j]; // 数据移动
j--;
} else {
break;
}
}
nums[j + 1] = value; // 插入数据
}
}

选择排序(Selection Sort)

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] nums) {
int length = nums.length;
if (length <= 1) {
return;
}
for (int i = 0; i < length; i++) {
int minIdx = i;
for (int j = i; j < length; j++) {
if (nums[minIdx] > nums[j]) {
minIdx = j;
}
}
int tmp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = tmp;
}
}

归并排序(Merge Sort)

归并排序就使用了分治的思想,先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

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
public static void mergeSort(int[] nums) {
int length = nums.length;
if (length <= 1) {
return;
}
mergeSort(nums, 0, length - 1);
}
private static void mergeSort(int[] nums, int left, int right) {
if (right <= left) {
return;
}
int mid = (left + right) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
private static void merge(int[] nums, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
System.arraycopy(tmp, 0, nums, left, tmp.length);
}

快速排序(Quick Sort)

快排也是利用分治的思想,先从数组中取标杆 pivot,将 pivot 小的元素放在 pivot 左边,大的元素放在 pivot 右边,然后依次对右边和右边的子数组继续用同样的方式排序,以达到整个序列有序。图中的例子选取 pivot 是待排数组的最右侧元素。

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
public static void quickSort(int[] nums) {
int length = nums.length;
if (length <= 1) {
return;
}
quickSort(nums, 0, length - 1);
}

private static void quickSort(int[] nums, int left, int right) {
if (left < right) {
int partitionIndex = partition(nums, left, right);
quickSort(nums, left, partitionIndex - 1);
quickSort(nums, partitionIndex + 1, right);
}
}

private static int partition(int[] nums, int left, int right) {
// pivot: 标杆位置,counter: ⼩于pivot的元素的个数
int pivot = right, counter = left;
for (int i = left; i < right; i++) {
if (nums[i] < nums[pivot]) {
int temp = nums[counter];
nums[counter] = nums[i];
nums[i] = temp;
counter++;
}
}
int temp = nums[pivot];
nums[pivot] = nums[counter];
nums[counter] = temp;
return counter;
}

堆排序(Heap Sort)

数组元素建立大顶堆,取出堆顶元素和堆尾元素交换,再重新调整成大顶堆

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
/**
* 堆排序
* @param nums 待排序数组
*/
public static void heapSort(int[] nums) {
int length = nums.length;
//初始化大顶堆
for (int i = (length - 2) / 2; i >= 0; i--) {
adjustHeap(nums, i, length);
}
//每次取堆顶元素与堆尾元素交换,再重新调整成大顶堆
for (int i = length - 1; i > 0; i--) {
int temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
adjustHeap(nums, 0, i);
}
}
/**
* 调整堆->大顶堆
*
* @param nums 待排序数组
* @param top 堆顶元素下标
* @param length 待调整的堆长度
*/
public static void adjustHeap(int[] nums, int top, int length) {
int temp = nums[top]; //暂存堆顶元素
//比较左右子树根结点,从大的子树向下遍历调整堆
for (int i = 2 * top + 1; i < length; i = i * 2 + 1) {
//保证i为较大的子树下标
if (i < length - 1 && nums[i] < nums[i + 1]) {
i++;
}
if (temp > nums[i]) {
break;
}
nums[top] = nums[i];
top = i;//向下搜索
}
nums[top] = temp;
}

总结

归并排序和快排都使用来分治的思想,区别是归并排序的处理过程是由下到上的,先处理子问题,然后再合并(merge),而快排正好相反,它的处理过程是由上到下的,先分区(partition),然后再处理子问题。

归并排序虽然时间复杂度很稳定,但是不是原地排序算法,空间复杂度为 O(n),所以它也没有快排应用广泛。快排虽然最坏情况下的时间复杂度是 O(n²),但是平均情况下时间复杂度是 O(nlogn)。而且快排时间复杂度退化到 O(n²) 的概率非常小,我们可以通过合理地选择 pivot 来避免这种情况。

排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(n) O(1) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
希尔排序 O(n^1.3) O(n²) O(n) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定
基数排序 O(n*k) O(n*k) O(n*k) O(n+k) 稳定

贪心

  • 适用范围(典型场景):
    针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。

  • 尝试用贪心算法解决:

    每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。

  • 举例验证结果是否是最优:

    大部分情况下,举几个例子验证一下就可以了,严格地证明贪心算法的正确性,是非常复杂的,需要涉及比较多的数学推理。

动态规划

适用范围(典型场景):

问题符合 一个模型三个特征 可以用动态规划方法解决。

  • 一个模型,即 多阶段决策最优解模型

    • 动态规划主要用来解决最优问题,解决问题的过程,需要经历多个决策阶段;
    • 每个决策阶段都对应着一组状态;
    • 然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。
  • 三个特征

    • 最优子结构
      • 可以通过子问题的最优解,推导出问题的最优解;
      • 后面阶段的状态可以通过前面阶段的状态推导出来。
    • 无后效性
      • 解决问题某阶段状态一旦确定,就不受之后阶段的决策影响。
    • 重复子问题
      • 不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态用同样的方式解决。

解题思路

  • 明确状态
    • 可以先尝试用回溯法解决问题,画出简单的递归树,以此来寻找重复子问题
    • 递归树的每个节点表示一个状态和 N 个变量
  • 明确选择
    • 每次决策选择最优的状态变量
  • 确定 base case
    • 当问题数据规模最小的时候,base case 是显而易见的,可以直接得出结果的
  • 写出递归方程
    • 根据状态定义和选择条件写出递归方程

代码模板

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1,选择2...)

总结

我解动态规划问题一般会把原问题数据规模缩小,然后逐步增加数据规模,通过具体的实例来思考问题,找到问题的规律,就像上一篇 零钱兑换问题 的题解一样,根据找到的规律总结出 状态转移表 ,写出一般的 DP 之后,再考虑状态转移表的压缩问题,进行空间复杂度的优化。

动态规划问题的一般就是求最值问题。首先也是找每个阶段 重复子问题,从子问题找的 最优子结构,这样才能通过子问题的最值得到原问题的最值。每个重复子问题都包含相同结构的 状态 ,我根据已知的最简单的子问题的解 base case,自底向上逐步扩大规模,根据 **状态转移方程 **逐步得到原问题的解。动态规划问题基本都可以用回溯来解决,只不过回溯算法解决起来效率比较低,时间复杂度是指数级的,而动态规划执行效率要高很多。

贪心算法可以理解为一种特殊的动态规划问题,贪心选择具有特殊的性质,但可以有严格的数学证明,通过每阶段的最优选择来降低动态规划算法的时间复杂度。

爬楼梯问题

为了和后面讲解的 零钱兑换 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 解题的关键还是要能够识别出状态,和写出状态转移方程,我们可以通过一些具体的例子,再范化为抽象的状态转移方程,有了方程再翻译成为代码就太轻松了。