C# DP solution


  • 0
    B
    using System;
    using System.Collections.Generic;
    
    public class Solution {
        public int CoinChange(int[] coins, int amount) {
           if (amount == 0) return 0;
            if(coins.Length==1){
                if(amount%coins[0]==0)
                    return amount/coins[0];
                else
                    return -1;
            }
          var r = cc(coins,amount,new Dictionary<int,int>());
            if(r==int.MaxValue)
                return -1;
            return r;
           
        }
        
        public int cc(int[] coins, int amount,Dictionary<int,int> dic) {
           if (amount == 0) return 0;
            if(dic.ContainsKey(amount)){
               return dic[amount];
            }
           int res = int.MaxValue;
           int n = coins.Length;
           for (int i=0; i<n; i++)
           {
             if (coins[i] <= amount)
             {
                 int subRes = cc(coins, amount-coins[i],dic);
                 if (subRes!= int.MaxValue && subRes + 1 < res)
                    res = subRes + 1;
             }
           }
           dic.Add(amount,res);
           return res;
        }
        
        
    }
    
    

Log in to reply
 

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