题目地址:
https://www.lintcode.com/problem/coin-change/description
给定若干硬币的面值,以数组 A A A形式给出,再给定一个金额 n n n,问至少要多少个硬币可以凑出 n n n这么多钱。如果凑不出来,则返回 − 1 -1 −1。
思路是动态规划。设 f [ i ] f[i] f[i]是凑出 i i i的面值至少需要多少个硬币,那么根据最后一个硬币选谁,我们可以进行分类,最后一个硬币可以选 A [ 0 ] , A [ 1 ] , . . . , A [ l A − 1 ] A[0],A[1],...,A[l_A-1] A[0],A[1],...,A[lA−1],所以 f [ i ] = 1 + min i ≥ A [ j ] f [ i − A [ j ] ] f[i]=1+\min_{i\ge A[j]}f[i-A[j]] f[i]=1+i≥A[j]minf[i−A[j]]如果凑不出来,我们规定 f [ i ] = ∞ f[i]=\infty f[i]=∞,所以在递推的时候还需要判断一下 i − A [ j ] i-A[j] i−A[j]是否能凑出来。代码如下:
public class Solution {
/**
* @param coins: a list of integer
* @param amount: a total amount of money amount
* @return: the fewest number of coins that you need to make up
*/
public int coinChange(int[] coins, int amount) {
// write your code here
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE;
// 枚举最后一个硬币选谁
for (int j = 0; j < coins.length; j++) {
if (i >= coins[j] && dp[i - coins[j]] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
时间复杂度 O ( l A n ) O(l_An) O(lAn),空间 O ( n ) O(n) O(n)。