C# easy DP / Memoization solution. Do you think memoization is faster than bottom up ?


  • 0
    G
    public class Solution {
    
    public int CoinChange(int[] coins, int amount) {
        if(coins == null || coins.Length == 0 || amount < 0){ return -1;}
        if(coins.Length == 1){ return amount % coins[0] == 0 ? amount/ coins[0] : -1;}
        
        var d = new Dictionary<int,int>();
        d.Add(0,0);
        
        return Helper(coins, amount, d);
    }
    
    private int Helper(int[] coins, int amount, Dictionary<int,int> d){
        if(amount < 0){ return -1;}
        if(d.ContainsKey(amount)){ return d[amount]; }
        
        var min = -1;
        foreach(var c in coins){
            var t = Helper(coins, amount- c, d);
            if(t==-1){ continue; }
    
            t++;
            min = t< min || min == -1 ? t : min;
        }
        
        d.Add(amount, min);
        return min;
    }
    }
    

    Time complexity = amount * coins.Length
    Space complexity = amount;

    I thinkt he top down approach ( memoization) beats the bottom up approach in this case as it will require less memory usage on average : the bottom up approach requires to declare an array of size n every time whereas the dictionary will contains only the sums of coins. in the worst case (there is a coin of value 1) the dictionary will contain as many numbers as the array.

    However, a dictionary<int,int> is about 5 time bigger than an array containing the same number of element (a dictionary contains, the key (32B), the value (32B), a pointer to the next key (64B) + probing space)

    What are your thoughts on this ?


  • 1

Log in to reply
 

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