Trying without DP first. Wrong Answer

#1

#include
#include
#include

using namespace std;

int coinschange(int *coins, int n, int m, set<vector>&s, vectorout){

if(n==0){

	if(s.find(out)!=s.end())
		return 0;
	
	s.insert(out);
	return 1;
	
}

if(n<0){
	return 0;
}

int ans=0;

for(int i=0; i<m; i++){

	out.push_back(coins[i]);

	ans+=coinschange(coins,n-coins[i],m,s,out);

	out.pop_back();

}

return ans;

}

int main(){

	int n;
	cin>>n;

	int m;
	cin>>m;

	int coins[m];

	for(int i=0; i<m; i++){

		cin>>coins[i];

	}

	set<vector<int>>s;

	vector<int>out;

	cout<<coinschange(coins,n,m,s,out);

return 0;

}

#2

@rachitbansal2500, kindly send your code using ide.codingblocks.com or any other ide

#3

Hi! The code is working fine without dp. I just don’t know how to include dp into this question please help https://ide.codingblocks.com/s/296212

#4

@rachitbansal2500, including dp in your solution will not work as you intend let me tell you how , dp is all about saving states and reusing them , but in your function you have n, out(which is a vector) and s(set) as variables whose values change so you have to save the state of these value too ,since out can take n values that means n variables making the time complexity as n*(a[i])^n which is too much , this must be confusing to you , what i simply mean is you have to reduce the state of your function , that means reducing the number of variables your function depends on
refer this :- https://ide.codingblocks.com/s/296384
notice that the function state only depends only on n and m
making the complexity of code as o(m*n)

1 Like
#5

Hi! Can you explain how are we ensuring that only unique combinations are being considered?

#6

Also can we do this the other way round? like you are picking coins from the end of the array, can I do it from the beginning instead?

#7

since we have initialized dp matrix with -1 , so we can easily check if we already stored this state then dp[n][m] will not be equal to -1 and we can just return dp[n][m],

yes , you can definitely do that , you can try it yourself

#8

I have another question! What does the ‘m’ variable here signify? What state is that? ‘n’ is storing the leftover value that we have to makeup, what is m exactly? Also, how did you know that this problem is of 2d dp? how did your intuition led up to this conclusion?

#9

@O17LPOLA020023 Please see to the doubt

#10

@rachitbansal2500, i was on one day break , sorry for late reply, basically m represents the range of values you are considering , that range is denoted by [0,m-1] , if you have coins like [ 2 5 3 6 ] and m=2 , this means you are only considering coins [2,5] (range: 0-1),
coming to your second question , how i decided the problem is of 2D dp , is simple , there are two values our state depends on 1. the value we have i.e. N , 2. the range of value we have i.e M , so we will get N*M unique states , so i made dp[N][M] , since N can take max value of 250 , and M can take max Value of 50 so i had dp[250][50] ,

In case of any doubt feel free to ask :slight_smile:

1 Like
#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.