Leetcode 322. Coin Change

tags: Leetcode(JAVA)

題目 : https://leetcode.com/problems/coin-change/ 。

想法 :

​​​​零錢問題。

時間複雜度 : O(m*n)。

程式碼 : (JAVA)

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[10010];
        
        for(int i=0 ; i<=amount ; i++){
            dp[i]=100010;
        }
        
        dp[0]=0;
        for(int i=0 ; i<coins.length ; i++){
            for(int j=coins[i] ; j<=amount ; j++){
                dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);
            }
        }
        
        return dp[amount] == 100010 ? -1 : dp[amount];
    }
}