零钱兑换问题
作者：Grey
原文地址:
题目描述
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
题目链接：LeetCode 322. Coin Change
暴力递归
定义递归函数
int p(int[] coins, int i, int rest)
递归含义是：从 i 往后自由选择，可以凑成 rest 的最少硬币个数是多少。
所以主函数只需要调用p(coins, 0, amount)就是答案。
接下来看递归方法的实现：
首先是 base case ，有如下三种情况
情况1，如果rest < 0，说明之前的决策有问题（如果决策没问题，不可能让 rest 小于0）。返回 -1，表示决策有问题；
情况2，如果rest == 0，说明之前的决策凑出了 amount，接下来不需要任何硬币，直接返回 0。
情况3，如果rest > 0，而此时，i == coins.length，说明 i 走到了尽头（没有硬币可选了），rest都不为空，直接返回 -1 即可。
接下来就是普遍情况，枚举每个位置硬币的数量 num 情况下，后续的最优解是什么，核心代码如下，关键就是 while 循环中的内容：
int min = Integer.MAX_VALUE;
int num = 0;
// 枚举每个位置的硬币个数，从 0 开始....
while (num * coins[i] <= rest) {
// 解决后续的钱数
int after = p(coins, i + 1, rest - num * coins[i]);
if (after != -1) {
min = Math.min(num + after, min);
}
num++;
}
return min == Integer.MAX_VALUE ? -1 : min;
暴力递归解法的完整代码如下：
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
return p(coins, 0, amount);
}
// 从i...往后自由选择，凑成rest的最少的硬币个数
public static int p(int[] coins, int i, int rest) {
if (rest < 0) {
return -1;
}
if (rest == 0) {
return 0;
}
// rest不为空
if (i == coins.length) {
// i 已经走到尽头
return -1;
}
// 既没有到最后，也还有剩余
int min = Integer.MAX_VALUE;
int num = 0;
while (num * coins[i] <= rest) {
int after = p(coins, i + 1, rest - num * coins[i]);
if (after != -1) {
min = Math.min(num + after, min);
}
num++;
}
return min == Integer.MAX_VALUE ? -1 : min;
}
使用暴力解，LeetCode 直接超时
动态规划
可以将上述的暴力递归解法改成动态规划的解，定义一个二维数组int[][] dp = new int[n + 1][amount + 1]，其中
dp[i][j]的含义就是硬币从 i 开始自由选择，一直到最后，能凑出 j 的硬币数量是多少
显然有
for (int i = 1; i < amount + 1; i++) {
dp[n][i] = -1;
}
即：无硬币情况下，只要 i 不等于 0，都不可能有选择，直接赋 -1。
接下来就是递归过程转换成动态规划的格子依赖，其中 while 循环就是枚举每个位置硬币有 num 枚的时候，最优解法是什么。
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j < amount + 1; j++) {
int min = Integer.MAX_VALUE;
int num = 0;
// 枚举行为，可以继续优化
while (num * coins[i] <= j) {
int after = dp[i + 1][j - num * coins[i]];
if (after != -1) {
min = Math.min(num + after, min);
}
num++;
}
dp[i][j] = (min == Integer.MAX_VALUE ? -1 : min);
}
}
完整代码如下
class Solution {
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int i = 1; i < amount + 1; i++) {
dp[n][i] = -1;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j < amount + 1; j++) {
int min = Integer.MAX_VALUE;
int num = 0;
// 枚举行为，可以继续优化
while (num * coins[i] <= j) {
int after = dp[i + 1][j - num * coins[i]];
if (after != -1) {
min = Math.min(num + after, min);
}
num++;
}
dp[i][j] = (min == Integer.MAX_VALUE ? -1 : min);
}
}
return dp[0][amount];
}
}
枚举优化
动态规划解中，以下 while 循环
int min = Integer.MAX_VALUE;
int num = 0;
// 枚举行为，可以继续优化
while (num * coins[i] <= j) {
int after = dp[i + 1][j - num * coins[i]];
if (after != -1) {
min = Math.min(num + after, min);
}
num++;
}
dp[i][j] = (min == Integer.MAX_VALUE ? -1 : min);
可以优化成如下形式
dp[i][j] = dp[i + 1][j];
if (j - coins[i] >= 0 && dp[i][j - coins[i]] != -1) {
if (dp[i][j] == -1) {
dp[i][j] = dp[i][j - coins[i]] + 1;
} else {
dp[i][j] = Math.min(dp[i][j - coins[i]] + 1, dp[i][j]);
}
}
完整代码见
class Solution {
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int i = 1; i < amount + 1; i++) {
dp[n][i] = -1;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 1; j < amount + 1; j++) {
dp[i][j] = dp[i + 1][j];
if (j - coins[i] >= 0 && dp[i][j - coins[i]] != -1) {
if (dp[i][j] == -1) {
dp[i][j] = dp[i][j - coins[i]] + 1;
} else {
dp[i][j] = Math.min(dp[i][j - coins[i]] + 1, dp[i][j]);
}
}
}
}
return dp[0][amount];
}
}