#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 1);
        for(int i=1; i<=amount; i++){
            int n = 0;
            for(int j=0; j<coins.size(); j++){
                if(i - coins[j] >= 0){
                    n += dp[i-coins[j]];
                }
            }
            dp[i] = n;
            cout<<i<<" "<<dp[i]<<endl;
        }
        return dp.back();
    }
 
int main() {
	// your code goes here
	vector<int> coins = {1,2,5};
	cout<<change(5, coins)<<endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGNoYW5nZShpbnQgYW1vdW50LCB2ZWN0b3I8aW50PiYgY29pbnMpIHsKICAgICAgICB2ZWN0b3I8aW50PiBkcChhbW91bnQrMSwgMSk7CiAgICAgICAgZm9yKGludCBpPTE7IGk8PWFtb3VudDsgaSsrKXsKICAgICAgICAgICAgaW50IG4gPSAwOwogICAgICAgICAgICBmb3IoaW50IGo9MDsgajxjb2lucy5zaXplKCk7IGorKyl7CiAgICAgICAgICAgICAgICBpZihpIC0gY29pbnNbal0gPj0gMCl7CiAgICAgICAgICAgICAgICAgICAgbiArPSBkcFtpLWNvaW5zW2pdXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBkcFtpXSA9IG47CiAgICAgICAgICAgIGNvdXQ8PGk8PCIgIjw8ZHBbaV08PGVuZGw7CiAgICAgICAgfQogICAgICAgIHJldHVybiBkcC5iYWNrKCk7CiAgICB9CgppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCXZlY3RvcjxpbnQ+IGNvaW5zID0gezEsMiw1fTsKCWNvdXQ8PGNoYW5nZSg1LCBjb2lucyk8PGVuZGw7CglyZXR1cm4gMDsKfQ==