Help with approach

#1

sol: https://ide.codingblocks.com/s/420289

prob: https://leetcode.com/problems/coin-change/

please tell the mistakes , it is working fine until I use the memoization

#2 
            for(int  i = 0; i < coins.size(); i++){
            if(amount >= coins[i]){
                int smallerAmount = amount  - coins[i];
               if(smallerAmount != INT_MAX)
                ans = min(ans,coinChange(coins, smallerAmount)) + 1;
            }
        }

if it is not possible to find the coinchange for smaller Amount the function return -1
and then you take min so it is always -1 and then you add 1 hence always your ans will be 0

correct one

 for(int  i = 0; i < coins.size(); i++){
                if(amount >= coins[i]){
                    int smallerAmount = amount  - coins[i];
                    int currAns=coinChange(coins, smallerAmount);
                    if(currAns!=-1)ans = min(ans,currAns);   
                }
            }
            if(ans != INT_MAX){
                dp[amount]  = ans+1;
            }
            else{
                dp[amount] =-1;
            }
        
        return dp[amount];

you code is not working
because dp array is not initialize with all -1
int dp[1000] = {-1}; this statement only set first element to -1 rest all remain 0
run this and see the output https://ide.codingblocks.com/s/420301

i have previously mention this point as well

Modified Code

this code give correct output for smaller testcases but give TLE for large
because of multiple recursive calls

#3

Correct Approach
Bottom Up DP

#4

oh okay so no matter what we do in the top down method it will exceed tle, this time I was able to understand, the code which was done in class was much simpler because of the lack of constraints, thanks

#5

NO that’s not completely true
top down is not efficient only because of recursive calls

many times topdown also works fine

but bottom up has always an edge over top down (in context of Time complexity)

but top down has also one advantage
when you have not enough memory to store all results in dp array
then top down is a good option

#6

here I was talking about this particular question only, but yeah sometimes it is easier to come up with top down approach

#7

if your doubt resolved
plz mark your doubt as resolved

#8

I know that you have already sent the sol but I’m not able to understand the reason for out of bounds error because we are checking if coin is greater than the amount, and whenever I’m not able to make change for a particular amount that is INT_MAX is still there I replace it with -1

#9 
for(int i = 1; i<=amount; i++){
            for(int j = 0; j < coins.size(); j++){
                **if(amount - coins[i] >= 0){**  // here it should be i (not amount)
                         dp[i] = min(dp[i],dp[ i - coins[j]] + 1);
                    }
                }
            if(dp[i] == INT_MAX){
                dp[i] = -1;
            }
        }
#10

Modified Code

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[100000];
        for(int i = 0; i<=amount; i++){
            dp[i] = INT_MAX;
        }
        dp[0] = 0;
        for(int i = 1; i<=amount; i++){
            for(int j = 0; j < coins.size(); j++){
                if(i - coins[j] >= 0){                 
                         if(dp[i-coins[j]]!=-1)dp[i] = min(dp[i],dp[ i - coins[j]] + 1);
                    }
                }
            if(dp[i] == INT_MAX){
                dp[i] = -1;
            }
        } 
        return dp[amount];
    }
        
       
    
};