解题思路

只有 1 分、2 分、3 分三种硬币，问把 N 分钱兑换成硬币，一共有多少种不同的兑法。

这是完全背包求方案数的题。 每种硬币可以用任意多次。

用动态规划：设 dp[j] 表示凑出 j 分钱一共有多少种方法。

1. 初始化 dp[0] = 1：凑 0 分只有一种方法，就是一枚硬币都不放
2. 依次考虑三种硬币（面值 1、2、3）：
   • 对每个金额 j，dp[j] = dp[j] + dp[j-面值]
   • 意思是：凑 j 分的方法 = 之前已经算出的方法 + 最后再放一枚这种硬币的方法
3. 因为每种硬币能用多次，金额要从小到大循环（完全背包的写法）

为什么要从小到大循环？ 如果从大到小，每种硬币最多只能用一次（01 背包）；从小到大，同一个面值可以反复被使用，正好符合硬币随便用的题意。

举例：凑 4 分钱，共有 4 种方法：1+1+1+1、1+1+2、2+2、1+3，所以答案是 4。

参考代码

#include <iostream>
using namespace std;

int dp[32770];  // dp[j] 表示凑出 j 分钱有多少种兑换方法

int main() {
    int n;
    cin >> n;

    dp[0] = 1;  // 凑 0 分只有 1 种方法：一枚硬币都不放

    // 硬币面值只有 1 分、2 分、3 分三种
    for (int k = 1; k <= 3; k++) {
        // 完全背包：金额从小到大循环，这样同一种硬币可以用多次
        for (int j = k; j <= n; j++) {
            // 凑出 j 分的方法 = 之前的方法 + 最后再放一枚 k 分硬币的方法
            dp[j] += dp[j - k];
        }
    }

    cout << dp[n];  // 输出凑出 n 分的总方法数
    return 0;
}

复杂度分析

• 时间复杂度：O(3×N)，三种硬币各扫一遍金额
• 空间复杂度：O(N)，一个 dp 数组