c++基础算法动态DP解决CoinChange问题

#include <iOStream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
long long recursion(vector<int> &coins, int money, int index, unordered_map<string, int> &memo){
	//终止条件2个
    if (0 == money)
        return 1;
    if (index >= coins.size() || money < 0)
        return 0;
    string key = to_string(money) + " , " + to_string(index);
    //如果记录中有的话就直接返回就好了
    if (memo.find(key) != memo.end())
        return memo[key];
    long long res = 0;
    int remaining = money;
    while(remaining >= 0){
        res += recursion(coins, remaining, index + 1, memo);
        remaining -= coins[index];
    }
    //记录一下
    memo[key] = res;
    return res;
}

long long make_change(vector<int> coins, int money) {
	//用哈希表来记录 <剩下的钱-用的硬币>:换硬币的组合数
    unordered_map<string, int> memo;
    long long res = recursion(coins, money, 0, memo);
    return res;
}

int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<int> coins(m);
    for(int coins_i = 0;coins_i < m;coins_i++){
       cin >> coins[coins_i];
    }
    cout << make_change(coins, n) << endl;
    return 0;
}

long long make_change(vector<int> coins, int money) {
    vector<long long> memo(money + 1, 0);
    memo[0] = 1;
    for (int i = 0; i < coins.size(); i++){
        for (int j = coins[i]; j <= money; j++){
            memo[j] += memo[j - coins[i]];
        }
    }
    return memo[money];
}

long long make_change(vector<int> coins, int money) {
	vector<long long> memo(money + 1, 0);
	memo[0] = 1;
	for (int i = 0; i < coins.size(); i++){
		//改动处：由从前往后改成了从后往前，略去了重复的情况
		for (int j = money; j >= coins[i]; j--){
			memo[j] += memo[j - coins[i]];
		}
	}
	return memo[money];
}

long long make_change(vector<int> coins, int money) {
	vector<long long> memo(money + 1, 0);
	memo[0] = 1;
	//改变了里外循环的顺序
	for (int i = 1; i <=money; i++){
		for (int j = 0; j < coins.size(); j++){
			if (i - coins[j] >= 0)
				memo[i] += memo[i - coins[j]];
		}
	}
	return memo[money];
}