Bottom Up; Time - O(NM); Space - O(N);


  • 0
    S
    public class Solution {
        public int CoinChange(int[] coins, int amount) {
            if(amount == 0 || coins.Length == 0)
            {
                return 0;
            }
            
            int len = coins.Length;
            var a = new int[amount+1];
            
            a[0] = 0;
            for(int i = 1; i < amount+1; i++)
            {
                a[i] = Int32.MaxValue-1;
            }
            
            for(int j = 0; j < len; j++) 
            {
                for(int i = 1; i <= amount; i++)
                {
                    if(i >= coins[j])
                        a[i] = Math.Min(a[i-coins[j]] + 1, a[i]);
                }
            }
            return a[amount] == Int32.MaxValue - 1 ? -1: a[amount];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.