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

• ``````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; }

t++;
min = t< min || min == -1 ? t : 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 ?

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