include

include

include

using namespace std;

vector coinChangeDP(const vector& coins, int amount) { vector dp(amount+1,numeric_limits::max()); dp[0]=0;

for(int i=1;i<=amount;i++)
{
    for(int j=0;j<coins.size();j++)
    {
        if(coins[j]<=i && dp[i - coins[j]] != numeric_limits<int>::max())
        {
            dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        }
    }
}
if(dp[amount]==numeric_limits<int>::max())
{
    return {-1};
}
else
{
    vector<int> result;
    int remaining = amount;
    while (remaining > 0) {
        for (int j = 0; j < coins.size(); j++) {
            if (remaining >= coins[j] && dp[remaining - coins[j]] == dp[remaining] - 1) {
                result.push_back(coins[j]);
                remaining -= coins[j];
                break;
            }
        }
    }
    return result;
}

} int main() { vector coin = {1,5,10,25}; int amount = 47;

cout<<"Dymanic Programming Approach Result: " <<endl;
vector<int> resultDP = coinChangeDP(coins,amount);
for(int i=0;i<resultDP.size();i++)
{
    cout<< resultDP[i]" ";
}
cout<<endl;
return 0;

}