输入：
[1, 2, 5]
11
输出： 3
解释： 11 = 5 + 5 + 1
样例2
输入：
[2]
3
输出： -1
题解
这是一个典型的完全背包问题，在《动态规划专题班》中侯卫东老师有详细讲解。设dpi表示使用前i个硬币，总金额为j时需要的最少硬币数量。 dp[i][j]=max(dp[i−1][j],dp[i−1][j−k∗coin[i]]+k)(0≤k∗coin[i]≤j)
public class Solution {
public int coinChange(int[] A, int M) {
int[] f = new int[M + 1];
int n = A.length;
f[0] = 0;
int i, j;
for (i = 1; i <= M; ++i) {
f[i] = -1;
for (j = 0; j < n; ++j) {
if (i >= A[j] && f[i - A[j]] != -1) {
if (f[i] == -1 || f[i - A[j]] + 1 < f[i]) {
f[i] = f[i - A[j]] + 1;
}
}
}
}
return f[M];
}
}
更多题解参考：九章官网solution