Dp problem help(Coin Combinations)

1

Screenshot (394)
Screenshot (394)717×793 28.1 KB

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

3

Probably MLE

4

@vaibhavgadag The problem was with your DP table, use 1D array instead of 2D table.

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.
    :slightly_smiling_face:
5

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';
}
6

That was something to be figured out later. :laughing:
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 :slightly_smiling_face: .

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;
}
7

Thanks Dude !! :grinning:

8

Thanks Dude