C++ 算法：300 元兑换零钱的方案数

这是一道典型的动态规划问题。

设 f[i][j][k][l] 表示前 i 个硬币，用了 j 个 10 元，k 个 5 元，l 个 1 元的方案数。

那么对于第 i 个硬币，它可以不用，也可以用。如果不用，那么 f[i][j][k][l] 就等于 f[i-1][j][k][l]；如果用，那么它可以用 10 元、5 元或 1 元的任意一种，设当前要用的面额为 x，则有：

f[i][j][k][l] += f[i-1][j-x/10][k-(x%10)/5][l-x%5] (x 为 10, 5, 1 中的一个)

最后的答案即为 f[3][1][1][149]，表示用 3 个硬币，1 个 10 元，1 个 5 元，149 个 1 元的方案数。

代码如下：

#include <iostream>
using namespace std;

int main() {
    int f[4][2][2][150] = {0};
    f[0][0][0][0] = 1;
    for (int i = 1; i <= 3; i++) {
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 1; k++) {
                for (int l = 0; l <= 149; l++) {
                    f[i][j][k][l] = f[i - 1][j][k][l];
                    if (j > 0) f[i][j][k][l] += f[i - 1][j - 1][k][l + 10];
                    if (k > 0) f[i][j][k][l] += f[i - 1][j][k - 1][l + 5];
                    if (l > 0) f[i][j][k][l] += f[i - 1][j][k][l - 1];
                }
            }
        }
    }
    cout << f[3][1][1][149] << endl;
    return 0;
}