"CSES — Coin Combinations I" how to solve using 2d matrix?

Правка en1, от Loser_, 2020-09-15 09:43:25

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;
}
Теги cses_helpline, #dynamic programing, bottom-up

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Loser_ 2020-09-15 09:43:25 1248 Initial revision (published)