1232: Coin Change (II)

It’s a classic problem

Ref: Geeksforfgeeks

View code

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

#define INF 10000000

typedef long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end()) // for set,map
#define present(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
const int mod=100000007;

int coin;
const int N=10010;
ll dp[N];
int ar[N],m;
int coinchange(int ar[],int m,int n)
{

memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=0;i<m;i++)
for(int j=ar[i];j<=n;j++) dp[j]=(dp[j]+dp[j-ar[i]])%mod; return dp[n]%mod; } int main() { int t,cs=1; cin>>t;
while(t–)
{
cin>>m>>coin;
for(int i=0;i<m;i++) { cin>>ar[i];
}
cout<<“Case “<<cs++<<“: “<<coinchange(ar,m,coin)<<endl;
}

}

 

Similar problem: uva 674

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s