Untitled

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

int minBills_backtracking(int n, int k, int *moneys){
    if(k==0) return 0;
    int result = INT_MAX;

    for(int i = 0; i< n; i++)
        if(moneys[i] <= k){
            int temp = minBills_backtracking(n, k - moneys[i], moneys);

            if(temp != INT_MAX)
                result=min(result, temp + 1);
        }
    return (result==INT_MAX?0:result);
}

int minBills_DP(int n, int k, int *moneys){
    int f[k+1];
    fill(f, f+k+1, INT_MAX);
    f[0] = 0;

    for(int i=1; i<=k; i++){
        for(int j=0; j<n; j++)
            if(moneys[j] <= i){
                int temp = f[i-moneys[j]];
                if(temp != INT_MAX);
                    f[i] = min(f[i], f[i-moneys[j]]+1);
            }
    }

    return (f[k]==INT_MAX?0:f[k]);
}

int main(){
    int moneys[] = {1,4,7,13,28,52,91,365};
    int n = sizeof(moneys)/sizeof(moneys[0]);
    int k;
    cin>>k;
    cout<< minBills_backtracking(n, k, moneys)<<endl;
    cout<< minBills_DP(n, k, moneys);
}