Cacher is the code snippet organizer for pro developers

#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;
    }
}