gopiariv / codeforces Goto Github PK

there is a tag of dp for the given question.
the dp solution is
`#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll a,b,c;
ll dp[1000000];
ll get(ll sum){

if(sum==0)
return 1;
else if(sum<0)
return -100000;
else if( dp[sum] != -1 )
return dp[sum];
else{
ll result=1+max(get(sum-a),max(get(sum-b),get(sum-c)));
dp[sum]=result;
return result;
}

}
ll ans( ll n ){

return max( get(n-a) ,max( get(n-b) , get(n-c ) ) );
}

int main(){

ll n;

cin>>n>>a>>b>>c;
memset(dp,-1,sizeof(dp));
cout<<ans(n)<<endl;

}`