零钱兑换问题
作者：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]; } } 
