Loser_'s blog

By Loser_, history, 4 years ago, In English

Hello.I was going through the problem Coin Combinations I which is similar to the next question Coin Combinations II.In Coin Combination II problem I used 2d array to store the dp values and used bottom up approach to solve it.The submission is here.Now I was wondering if Coin Combination I has the similar solution like II using 2d array ? I have gone through many solutions but none of these have used 2d array.So I could not come up with any idea.Please help me with this.

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,sum;
    cin>>n>>sum;
    vector<int>v(n);
    for(int i=0;i<n;++i)
    {
        cin>>v[i];
    }
    int dp[n+1][sum+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=sum;++j)
        {
        	if(j>=v[i-1])
        	{
        		//Condition
        		dp[i][j]%=mod;
		}
        }
    }
    cout<<dp[n][sum]<<endl;
    return 0;
}
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I told it before , if it is possible to use 2d array here to solve it.If not then why?I have already solve it using 1d array

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my bad.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How exactly do you want to use a 2d array?

      If you do something like dp[n + 1][sum + 1]
      That will give you the number of ways of getting a sum $$$s(1 <= s <= n)$$$ from the first i values
      So you aren't going to count all the distinct ways
      You will count each way just once

      For the sample input in the problem, you will have
      2 + 2 + 5 = 9
      3 + 3 + 3 = 9
      2 + 2 + 2 + 3 = 9

      And that's just 3 ways