Leetcode -- 322. Coin Change(DP)

322. Coin Change(DP)
Medium
https://leetcode.com/problems/coin-change/#/description

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

思路：-  use dp bottom up, memoization method
          - we know each solution is formed by at least 1 existing coin, so we check if dp[i-coin] exists.
          - keep filling dp[i] with the min
Complexity: Time O(m*n) -  m is amount, n is len of coins,  Space O(m) - dp array

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];//0,1,2,..,amount
        for(int i = 1; i <= amount; i++){
            int count = -1;
            //key is min count, all solutions must be generated from existing coin
            for(int coin : coins) {
             if(i >= coin && dp[i-coin]!=-1) {//skip non-existing solution
              int cur = dp[i-coin]+1;
              if(count < 0)
                  count  = cur;
              else if(cur < count)
                  count = cur;
             }
         }
         dp[i] = count;
        }
        return dp[amount];
    }