零钱问题c++

零钱问题是一个经典的动态规划问题。假设你有 $n$ 种不同面值的硬币，每种硬币的数量无限。现在你需要用这些硬币来凑出总价值为 $m$ 的零钱。求出总共有多少种凑法。

可以使用动态规划来解决这个问题。定义状态 $dp[i]$ 表示凑出价值为 $i$ 的零钱的总方案数。状态转移方程为：

$$ dp[i] = \sum_{j=0}^{n-1} {dp[i-coins[j]]} $$

其中 coins 是硬币面值的数组，n 是硬币种类的数量。这个方程的意思是，如果我们要凑出 $i$ 的零钱，可以选择任意一枚硬币 $coins[j]$，然后再凑出剩下的 $i-coins[j]$ 的零钱。因此总方案数就是选择每一种硬币的方案数之和。

具体实现时，需要初始化 $dp[0]=1$，因为凑出价值为 $0$ 的零钱只有一种方案，就是不选任何硬币。同时需要注意内外层循环的顺序，因为外层循环枚举的是硬币种类，内层循环枚举的是要凑出的零钱金额，所以必须先枚举硬币种类，再枚举金额。

下面是 C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }
    vector<int> dp(m + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= m; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    cout << dp[m] << endl;
    return 0;
}

其中，输入的第一行是两个整数 $n$ 和 $m$，分别表示硬币种类的数量和要凑出的零钱金额。接下来 $n$ 行是每种硬币的面值。输出的是凑出总价值为 $m$ 的零钱的方案数。