pranay_teja
11/27/2018 - 7:10 AM

## CoinChange-MinCoins

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

// #DynamicProgramming #StandardProblem
// https://codingblocks.com/resources/dp-webinar/

//============( Recursion )======================
int minCoins(int sum, vector<int> coins){
if(sum==0){
return 0; // 0 coins needed to make sum 0
}

int minimumCoins=INT_MAX;
// at every point sum has n branches
// 15 {1,7,10} = 1 + {14,8,5}
// 15 can be reached from 3 previous paths with given coins
for(int i=0;i<coins.size();i++){
if(sum-coins[i]>=0){
int remaining=sum-coins[i];
minimumCoins = min(minimumCoins, 1 + minCoins(remaining,coins) );
}
}
return minimumCoins; // if there's no way to make change INT_MAX is returned
}

//====================( BottomUp )===================
int minCoinsBU(int sum, vector<int> coins){
vector<int> dp(sum+1, 0); // [0,n]
dp[0]=0; // 0 coins needed to make sum 0

for (int amount = 1; amount <= sum; amount++) {
dp[amount]=INT_MAX; // initialize as INT_MAX as we need min
for(int i=0;i<coins.size();i++){
if(amount-coins[i] >= 0){
int remaining=amount-coins[i];
dp[amount] = min( dp[amount], 1+ dp[remaining]);
}
}
}
return dp[sum];
}

int main(){
freopen("ip.txt","r",stdin);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> coins(n);
for(int i=0;i<n;i++){
cin>>coins[i];
}
int sum;
cin>>sum;
cout<<"Recursion : "<<minCoins(sum,coins)<<endl;
cout<<"BottomUp: "<<minCoinsBU(sum,coins)<<endl;
}
}
``````