纸币问题 2

题意

有 $n$ 种面额互不相同的纸币，第 $i$ 种面额为 $a_i$ ，每种无限张。要凑出金额 $w$ （ $1 \leqslant w \leqslant 10^4$ ），求支付方案数。同样的纸币组合如果支付顺序不同，算不同方案。 答案对 $10^9+7$ 取模。

原题对象	背包含义
一种纸币	一个可以重复使用的物品
面额 $a_i$	物品体积
支付顺序	排列（有序序列）
凑出金额 $w$	恰好装满容量 $w$

思路

一句话本质： 求完全背包的排列计数——先枚举金额再枚举纸币，让不同顺序自然产生不同方案。

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41// brute.cpp：小数据暴力解，递归枚举所有纸币支付序列，统计方案数（排列，顺序不同算不同方案）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MOD = 1000000007;

int n;          // 纸币种类数
int w;          // 要凑出的金额
int a[MAXN];    // 每种纸币的面额
int answer;     // 方案数

// remain：还需要凑的金额
// 每次递归选择一张纸币，继续凑剩余金额
void dfs(int remain) {
    if (remain == 0) {
        answer = (answer + 1) % MOD;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (remain >= a[i]) {
            dfs(remain - a[i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    answer = 0;
    dfs(w);
    cout << answer << '\n';

    return 0;
}

这个暴力从 $w$ 出发，每次任选一张面额不超过剩余金额的纸币，递归到 0 时统计一种方案。它枚举了所有支付序列，复杂度指数级。

这个递归在反复计算什么？

对于同一个剩余金额 remain，无论之前经历了哪条路径到达这里，后续的支付序列选择是完全一样的。例如凑 10 元，先付 1 再付 9 和先付 9 再付 1，两种路径都会到达 remain=0，但"从 10 到 0"的所有序列被重复枚举了很多次。

怎么避免重复枚举，同时又要保留"顺序不同算不同方案"的要求？

设 $dp[j]$ 表示恰好凑出 $j$ 元的方案数。 $dp[0]=1$ （什么都不付有一种方案）。要凑出 $j$ 元，最后一步可以付任意一张面额 $a_i$ 的纸币。最后一步之前，已经凑出了 $j-a_i$ 元，而那个状态有多少种排列，最后一步就能接出多少种新的排列：

dp[j] = \sum_{i=1}^{n} dp[j-a_i] \quad (\text{对所有 } j \geqslant a_i)

这个求和就是先枚举金额 $j$ ，再枚举纸币 $i$ 。

为什么不能先枚举纸币再枚举金额？

如果先枚举纸币再枚举金额（ $j$ 正序），对于纸币 $a_i$ ， $dp[j]$ 只会从 $dp[j-a_i]$ 转移，而此时的 $dp[j-a_i]$ 中只包含前 $i$ 种纸币的方案。这样做会约定纸币的使用顺序必须按编号递增，导致不同顺序被合并成一种组合——那是纸币问题 3 的做法。先枚举金额，每次把 $n$ 种纸币都当作可能的最后一步，自然保留了所有排列。

DP 公式

设 $dp_j$ 表示凑出金额 $j$ 的支付方式数（排列）。初始化 $dp_0 = 1$ ，其余 $dp_j = 0$ ：

dp_j = \sum_{i=1}^{n} dp_{j-a_i} \quad (j \geqslant a_i)

先枚举 $j = 1 \dots w$ ，内层枚举 $i = 1 \dots n$ 。最终答案为 $dp_w$ 。

样例 DP 表格

以样例 2 为例： $n=3, w=15$ ，面额 $1, 5, 11$ 。展示关键转移：

$j$	$dp[1]$	$dp[5]$	$dp[6]$	$dp[10]$	$dp[11]$	$dp[12]$	$dp[15]$
初始	0	0	0	0	0	0	0
$j=1$	$dp[0]=1$	—	—	—	—	—	—
$j=5$	—	$dp[4]+dp[0]=0+1=1$	—	—	—	—	—
$j=6$	—	—	$dp[5]+dp[1]=1+1=2$	—	—	—	—
$j=10$	—	—	—	$dp[9]+dp[5]=5+1=6$	—	—	—
$j=11$	—	—	—	—	$dp[10]+dp[6]+dp[0]=6+2+1=9$	—	—
$j=12$	—	—	—	—	—	$dp[11]+dp[7]+dp[1]=9+4+1=14$	—
$j=15$	—	—	—	—	—	—	$dp[14]+dp[10]+dp[4]=29+6+0=35$

最终 $dp[15] = 35$ 。（表格中的中间值 $dp[4], dp[9]$ 等均由其前面的状态递推得到。）

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXW = 10005;
const int MOD = 1000000007;

int n;                // 纸币种类数
int w;                // 要凑出的金额
int a[MAXN];          // 每种纸币的面额
int dp[MAXW];         // dp[j] = 凑出金额 j 的方案数（不同顺序算不同方案）

void read_input() {
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
}

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    // 先枚举金额再枚举纸币，这样不同顺序会被算作不同方案。
    for (int j = 1; j <= w; j++) {
        for (int i = 1; i <= n; i++) {
            if (j >= a[i]) {
                dp[j] = (dp[j] + dp[j - a[i]]) % MOD;
            }
        }
    }

    cout << dp[w] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(nw)$
空间复杂度： $O(w)$

总结

这题的关键是区分"排列计数"与"组合计数"的循环顺序：

先金额后纸币（本题）： 排列，不同顺序算不同方案
先纸币后金额（纸币问题 3）： 组合，不同顺序合并为同一种

两者代码几乎一模一样，只是两层循环交换了位置。把这一对题目放在一起对比，是理解完全背包计数循环含义的最好方式。

目录

题意

思路

DP 公式

样例 DP 表格

代码

复杂度

总结