322 Coin Change

Leetcode

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

---

dp[i] 表示组成金额 i 需要最少的硬币数，若为 -1 表示无法组合。 dp[0] 为 0 ，对于每一个数字进行遍历，尝试所有的硬币，看是否可以组合成这个金额，如果可以且金额小，更新 dp 。时间复杂度 o(m n) 空间复杂度 o(m n)

    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        for(int i=1;i<=amount;++i){
            dp[i]=-1;
        }
        for(int i=1;i<=amount;++i){
            for(int j=0;j<coins.length;++j){
                int cur=coins[j];
                if(i>=cur && dp[i-cur]!=-1){
                    if(dp[i]==-1 || dp[i]>dp[i-cur]+1) dp[i]=dp[i-cur]+1;
                }
            }
        }
        return dp[amount];
        
    }