I am facing `Time Limit Exceeded` in the problem **Coin Combinations II** of [cses](cses.fi).↵
↵
Code: ↵
↵
<spoiler summary="Full code">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define nl '\n'↵
#define all(v) v.begin(), v.end()↵
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
const ll MOD = 1000000007;↵
int n, x, dp[1000001][101];↵
vector<int> c;↵
int rec(int x, int r){↵
if(x == 0) return 1;↵
if(x < 0 || r < 0) return 0;↵
if(dp[x][r]!=-1) return dp[x][r];↵
int ans = 0;↵
ans += rec(x-c[r], r) + rec(x, r-1), ans%=MOD;↵
return dp[x][r]=ans;↵
}↵
void solve(){↵
cin >> n >> x; c.resize(n);↵
for(int i=0; i<=x; ++i) for(int j=0; j<n; ++j) dp[i][j]=-1;↵
for(int i=0; i<n; ++i) cin >> c[i];↵
cout << rec(x, n-1);↵
}↵
signed main(){↵
IOS↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
My approach:↵
We define _rec(x, r)_ as the number of ordered ways to make a sum _x_ by using up to _rth_ coin (0-indexing). Now we are iterating from the last coin. We can either take _rth_ coin and add up _rec(x — c[r], r)_ to our answer or we can not take the _rth_ coin and simply add up _rec(x, r-1)_ (the answer by taking up to _(r-1)th_ coin). So we have:↵
↵
`dp[i][j] = dp[i - c[j]][j] + dp[i][j - 1]`↵
↵
We also do `dp[i][j] %= MOD` to prevent overflow. ↵
↵
What could be the possible reason for `Time Limit Exceeded`?↵
Thank you. ↵
↵
**UPD:** One person in the comments told that it is because constraints on CSES are tight and that's why recursion might give a TLE on CSES. I think that answers the question. ↵
↵
Code: ↵
↵
<spoiler summary="Full code">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long ↵
#define nl '\n'↵
#define all(v) v.begin(), v.end()↵
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
const ll MOD = 1000000007;↵
int n, x, dp[1000001][101];↵
vector<int> c;↵
int rec(int x, int r){↵
if(x == 0) return 1;↵
if(x < 0 || r < 0) return 0;↵
if(dp[x][r]!=-1) return dp[x][r];↵
int ans = 0;↵
ans += rec(x-c[r], r) + rec(x, r-1), ans%=MOD;↵
return dp[x][r]=ans;↵
}↵
void solve(){↵
cin >> n >> x; c.resize(n);↵
for(int i=0; i<=x; ++i) for(int j=0; j<n; ++j) dp[i][j]=-1;↵
for(int i=0; i<n; ++i) cin >> c[i];↵
cout << rec(x, n-1);↵
}↵
signed main(){↵
IOS↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
My approach:↵
We define _rec(x, r)_ as the number of ordered ways to make a sum _x_ by using up to _rth_ coin (0-indexing). Now we are iterating from the last coin. We can either take _rth_ coin and add up _rec(x — c[r], r)_ to our answer or we can not take the _rth_ coin and simply add up _rec(x, r-1)_ (the answer by taking up to _(r-1)th_ coin). So we have:↵
↵
`dp[i][j] = dp[i - c[j]][j] + dp[i][j - 1]`↵
↵
We also do `dp[i][j] %= MOD` to prevent overflow. ↵
↵
What could be the possible reason for `Time Limit Exceeded`?↵
Thank you. ↵
↵
**UPD:** One person in the comments told that it is because constraints on CSES are tight and that's why recursion might give a TLE on CSES. I think that answers the question. ↵
