题目地址：

https://www.lintcode.com/problem/coin-change/description

给定若干硬币的面值，以数组$A$形式给出，再给定一个金额$n$，问至少要多少个硬币可以凑出$n$这么多钱。如果凑不出来，则返回$-1$。

思路是动态规划。设$f[i]$是凑出$i$的面值至少需要多少个硬币，那么根据最后一个硬币选谁，我们可以进行分类，最后一个硬币可以选$A[0],A[1],...,A[l_A-1]$，所以$$f[i]=1+\underset{i\ge A[j]}{\min }f[i-A[j]]$$如果凑不出来，我们规定$f[i]=\infty$，所以在递推的时候还需要判断一下$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(n)$。