# Dp problem help(Coin Combinations)

My solution:
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{

``````ll sum,n;
cin>>n>>sum;
ll value[n];
for(int i=0;i<n;i++)
{
cin>>value[i];

}
ll dp[n+1][sum+1];
for(ll i=0;i<=n;i++)
{
for(ll j=0;j<=sum;j++)
{
if(j!=0 and i==0)
{
dp[i][j]=0;
}
if(j==0)
{
dp[i][j]=1;
}
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=sum;j++)
{
if(j-value[i-1]>=0)
{
dp[i][j]=(dp[i][j-value[i-1]]%1000000007+dp[i-1][j]%1000000007)%1000000007;
}
else
{
dp[i][j]=dp[i-1][j]%1000000007;
}
}
}
cout<<dp[n][sum]%1000000007;

return 0;
``````

}

Its not running for large inputs
E.g)100 1000000
27 69 68 13 1 63 28 44 45 67 57 11 8 85 42 20 32 77 39 52 70 24 4 79 7 15 54 88 51 73 89 66 48 56 47 18 2 30 21 49 74 9 99 83 55 95 62 90 22 31 71 98 43 75 25 16 12 64 61 38 40 26 3 96 41 86 5 14 91 33 78 50 23 84 94 36 46 97 53 81 65 34 93 59 6 35 72 10 82 60 19 92 29 87 76 100 80 17 58 37

plz help me to figure out what’s wrong on the code

Probably MLE

Some suggestions:

1. Post the link to the problem (no need to make any efforts taking the screenshot).
2. Consider formatting your code correctly.
3. Use memset whenever possible (looks better, a preference rather than a necessity).
4. And yes, instead of using 1000000007, consider using const int MOD = 1e9+7; , then type MOD wherever you need 1000000007.

2d won’t work because you can’t store 1e8 values in a vector.
My 1d solution:

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <class T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

void usaco(string name = "")
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(name.size())
{
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}

int main()
{
usaco();
int n, x;
cin >> n >> x;
vector <long long> v(n), dp(1000001);
dp[0] = 1;
for (int i = 0; i < n; ++i) cin >> v[i];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= x; ++j)
{
if (j < v[i]) continue;
else dp[j] += (dp[j-v[i]]), dp[j] %= 1000000007;
}
}
cout << dp[x] << '\n';
}
``````

That was something to be figured out later.
I just checked, using 2D gives RE. Even I had solved this problem using 1D, never tried 2D for this until now. Thanks @therealnishuz for that information .

My code:

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

const int MOD = 1e9+7;

int main()
{
int n, x;
cin >> n >> x;
vector<int> coins(n);
for(auto &i : coins) cin >> i;
vector<int> dp(x+1,0);
dp[0] = 1;
for(int i=1; i<=n; i++)
{
for(int j=0; j<=x-coins[i-1]; j++)
{
dp[j+coins[i-1]] += dp[j];
if(dp[j+coins[i-1]] >= MOD)
dp[j+coins[i-1]] -= MOD;
}
}
cout << dp[x]%MOD << "\n";
return 0;
}
``````

Thanks Dude !!

Thanks Dude