educative.io

Why do we need a 2d array for the top down solution

Courses
,
#1

I tried to use a 1 d array of only the amount and minimum number of coins to get to that amount but my solution fails for this input . Can I get an explanation on how using 2d array of coins,amount is resolving this :
Coins : [357,239,73,52]
Amount = 9832

class Solution {
public:
    int helper(vector<int>& coins, int amount, int i, vector<vector<int>>& dp) {
        if (i >= coins.size() && amount > 0) return INT_MAX;
        if (amount < 0) return INT_MAX;
        if (!amount) return 0;
         
       if (dp[amount] != -1) {
           return dp[amount];
       }
        int min1 = helper(coins, amount-coins[i], i, dp);
        if (min1 != INT_MAX) min1++;
        int min2 = helper(coins, amount, i+1, dp);
        if (min1 < min2) dp[amount] = min1;
        else dp[amount] = min2;
        return dp[amount];
    
    }
    
    int coinChange(vector<int>& coins, int amount, int i = 0) {
        std::vector<vector<int>> dp(amount+1, vector<int>(amount+1, -1));
        int ans =  helper(coins, amount, 0, dp);
        if (ans == INT_MAX) return -1;
        return ans;
    }
};
#2

Hi @pink_chink, hope you are doing well.

I think the problem of your solution is that you overwrite the value dp[Index][Total-denominations[Index]]. Note that, the formula takes into account two values, the last minimum for the current amount and the difference between current amount and the current coin value plus one. By using a single array, you don’t have all the necessary data to calculate both values and, therefore, how to get the minimum of both.

min( dp[Index-1][Total], dp[Index][Total-denominations[Index] + 1)

Hope that helps.

Artur Baruchi