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

  • 0
    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>();
        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; }
            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.