算法面试真题详解：换硬币

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

在线评测地址：领扣题库官网

样例1

输入：
[1, 2, 5]
11
输出： 3
解释： 11 = 5 + 5 + 1

样例2

输入： 
[2]
3
输出： -1

题解

这是一个典型的完全背包问题，在《动态规划专题班》中侯卫东老师有详细讲解.

设dpi表示使用前i个硬币，总金额为j时需要的最少硬币数量。
dpi=max(dpi−1,dpi−1]+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