【Lintcode】669. Coin Change

題目位址：

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]min​f[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(lA​n)，空間 O ( n ) O(n) O(n)。