Combination Sum (NUVO2019)

general
1

So i was solving this question and found it is similar to a famous DP problem.
I was using the algorithm:

nums=[1,2,4]
dp[0]=1
for i=1 to p-d:
   for x in nums:
       dp[i+x]+=dp[i]

I tried coding this but i was unable to :confused:
Can somebody help?

2

Some points:

1.) dp[i]+=dp[i-nums[j]] is the correct way.
2.) Test case constraint is too high, try to apply dp, outside the test cases.(find values till 1e5+5)
3.) problem could be solved without dp, if you write it on a sheet of paper(there is some sort of pattern)

Here’s my dp approach(it’s in C++):

#include <bits/stdc++.h>
using namespace std;

int main() {

int teams[3]={1,2,4};

long long dp[100005]={0};//intialise dp here
	dp[0]=1; //for 0 it's 1 way

	for(int i=0;i<3;i++)
		for(int j=teams[i];j<=100005;j++) //precomp values
			dp[j]+=dp[j-teams[i]];   //correct way

int t;cin>>t;while(t--){  //test cases

	int n,bot;cin>>n>>bot;

	int val=n-bot;  //real players
	cout<<dp[val]<<"\n";  //sol
}

return 0;
}
2 Likes
3

nums=[1,2,4]
dp[0]=1
for i=1 to p-d:
for x in nums:
dp[i+x]+=dp[i]
why this approach is wrong?
what happen if I write dp[i]+=dp[i-x] on the last line instead of dp[i+x]+=dp[i]?