# Similar to Coin Change II Problem

#1

Just think like, Coin Change II problem.

``````
#include <bits/stdc++.h>
using namespace std;
#include <chrono>
#ifndef mehul
#pragma GCC optimize("Ofast")
#endif

typedef long long ll;
typedef unordered_map<int, int> umapii;
typedef unordered_map<int, bool> umapib;
typedef unordered_map<string, int> umapsi;
typedef unordered_map<string, string> umapss;
typedef map<string, int> mapsi;
typedef map<pair<int, int>, int> mappiii;
typedef map<int, int> mapii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unordered_set<int> useti;

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define uset unordered_set
#define it iterator
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second

#define INF 4557430888798830399ll
#define MOD 1000000007
#define EPS 1e-7
#define PI acos(-1)

#define sz(x) (int)(x).size()

#define fr(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define frr(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define trav(a, x) for(auto& a : x)
#define fil(ar, val) memset(ar, val, sizeof(ar))  // 0x3f for inf, 0x80 for -INF can also use with pairs

int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
int a = A.size();
int b = B.size();
int c = C.size();

int mfc = *max_element(all(A));

vector<vector<int>>dp(mfc+1, vector<int>(b, 0));
//Fill for j = 0 ---> when only till dish 1;
fr(i,1, mfc){
if (i%B[0]!=0)
{
dp[i][0] = INT_MAX;
}else{
dp[i][0] = C[0]*(i/B[0]);
}
}
//fill from 1, 1 to mfc, b
fr(i, 1, mfc){
fr(j, 1, b-1){
int v1 = dp[i][j-1];
int v2 = (i-B[j]>=0 && dp[i-B[j]][j]!=INT_MAX)?(dp[i-B[j]][j]+C[j]):(INT_MAX);
dp[i][j] = min(v1, v2);
}
}

int ans = 0;
rep(i, a){
ans+=dp[A[i]][b-1];
}

return ans;

}
``````