#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
int countChange(const vector<int> &coins, int amount){
if(amount == 0) return 1;
vector<int> dp(amount + 1, 0);
for(int start = 0; start < coins.size(); start++){
for(int amt = 0; amt <= amount; amt++){
if(amt == 0) dp[amt] = 1;
else{
ll ways = dp[amt];
int leftAmt = amt - coins[start];
if(leftAmt >= 0) ways = (ways + dp[leftAmt])%MOD;
dp[amt] = ways;
}
}
}
return dp.back();
}
int main(){
int t; scanf("%d", &t);
while(t--){
int n,amount; scanf("%d", &n);
vector<int> arr(n);
for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
scanf("%d", &amount);
printf("%d\n",countChange(arr, amount));
}
return 0;
}
Need help, Getting TLE on 2 test cases
in your count change function your inner for loop is incorrect . use the below code instead.
// table[i] will be storing the number of solutions for
// value i. We need n+1 rows as the table is constructed
// in bottom up manner using the base case (n = 0)
ll table[n+1];
// Initialize all table values as 0
memset(table, 0, sizeof(table));
// Base case (If given value is 0)
table[0] = 1;
// Pick all coins one by one and update the table[] values
// after the index greater than or equal to the value of the
// picked coin
for(ll i=0; i<m; i++){
for(ll j=S[i]; j<=n; j++){
table[j] += table[j-S[i]];
table[j] %= mod;
}
}
return table[n];