Need help with money change problem

Revision en3, by vikalp14, 2018-07-31 14:51:39

Problem_link

Given a big amount N and the array of denominations S. Assuming infinite supply of each of S = {S1,S2….Sm} denominations, find the number of ways to make change for N cents.

Input Format: First line contains an integer T denoting the total number of test cases. For every test case, there are three lines. First line will contain an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, …, Am denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

Constraints: 1 <= T <= 10 1 <= n <= 100 1 <= S[i] <= 1000 1 <= N <= 1000000 Output Format: Print number of possible ways to make change for N cents in a new line. Since answers can be large, print answer % (1000000000 + 7).

Sample Input: 2 3 1 2 3 4 4 2 5 3 6 10 Sample Output: 4 5 Explanation: For N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

I am getting WA for t-1 test cases ,though I think the code is fine ?!


#include<bits/stdc++.h> using namespace std; #define ll long long ll dp[1000006]; int main() { ll t; cin>>t; while(t--) { ll n; cin>>n; int v[100]; for(int i=0 ; i<n ; i++) cin>>v[i]; ll s; cin>>s; for(int i=0;i<=s;i++) dp[i]=0; dp[0]=1; for(int i=0 ;i<n ;i++) { for(int j=v[i];j<=s;j++) { dp[j] = (dp[j]%1000000007 + dp[j-v[i]]%1000000007) % 1000000007; } } cout<<(dp[s])<<"\n"; } }

Fixed modulo T0 and T1 are AC But getting run time error for the rest T-2 test cases

Tags #dynamic-programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English vikalp14 2018-07-31 14:51:39 150 Modulo for every sum
en2 English vikalp14 2018-07-30 22:26:17 6
en1 English vikalp14 2018-07-30 22:25:16 1749 Initial revision (published)