518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例
-
输入：amount = 5, coins = [1, 2, 5]
-
输出：4
-
解释：有四种方式可以凑成总金额：
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
-
输入：amount = 3, coins = [2]
-
输出：0
-
解释：只用面额 2 的硬币不能凑成总金额 3。
-
输入：amount = 10, coins = [10]
-
输出：1
约束条件
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
public int change(int amount, int[] coins) {
// dp[i] 表示凑成金额 i 的组合数
int[] dp = new int[amount + 1];
dp[0] = 1;
// 外层循环遍历硬币（物品）
for (int i = 0; i < coins.length; i++) {
// 内层循环遍历金额（背包容量），正序遍历
for (int j = coins[i]; j <= amount; j++) {
// 状态转移：使用当前硬币 coins[i] 的组合数
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
解题思路
dp 数组代表装满背包的方式种类。初始化 dp[0] 设定为 1，这是后续递推的基础。递推公式如下：dp[j] += dp[j - coins[i]]。
这是一个完全背包问题：硬币可以无限使用 → 完全背包求组合数 → 计数类 DP。
关键点：这里求的是组合（不考虑顺序），不是排列。
- 组合数：外层循环硬币、内层循环金额。
- 排列数：外层循环金额、内层循环硬币。
例如 coins=[1,2]，amount=3：
- 只统计
(1,1,1)和(1,2)，不会把(2,1)算作另一种。
核心区别：组合 vs 排列
| 组合 | 排列 | |
|---|---|---|
| 定义 | 不考虑顺序，{1,2} 和 {2,1} 算同一种 | 考虑顺序，[1,2] 和 [2,1] 算不同 |
| 外层循环 | 硬币 | 金额 |
| 内层循环 | 金额 | 硬币 |
图示对比
假设 coins = [1, 2]，amount = 3
✅ 外层循环硬币（组合）
for (int coin : coins) { // 先固定硬币 1，再硬币 2
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
执行过程：
| 步骤 | 操作 | dp 数组变化 | 含义 |
|---|---|---|---|
| 初始 | - | [1,0,0,0] | 只有金额 0 有 1 种方法 |
| 用硬币 1 | 更新 dp[1],dp[2],dp[3] | [1,1,1,1] | 全用 1：(1,1,1) |
| 用硬币 2 | 更新 dp[2],dp[3] | [1,1,2,2] | 加 (1,2) |
结果 = 2 种组合：(1,1,1)、(1,2)
关键：硬币 1 处理完才处理硬币 2，不可能出现 2 在 1 前面。
❌ 外层循环金额（排列）
for (int j = 1; j <= amount; j++) { // 先固定金额
for (int coin : coins) { // 再遍历硬币
if (j >= coin) dp[j] += dp[j - coin];
}
}
执行过程：
| 金额 j | 遍历硬币 | 计算 dp[j] | 得到的方式 |
|---|---|---|---|
| 1 | 1,2 | dp[1]=dp[0]=1 | (1) |
| 2 | 1,2 | dp[2]=dp[1]+dp[0]=1+1=2 | (1,1)、(2) |
| 3 | 1,2 | dp[3]=dp[2]+dp[1]=2+1=3 | (1,1,1)、(1,2)、(2,1) |
结果 = 3 种排列：(1,1,1)、(1,2)、(2,1)。
根本原因：状态定义不同
组合（外层硬币）
dp[j] = 用 [已遍历的硬币] 凑成 j 的组合数
- 第 1 轮：dp[j] = 只用硬币 1 凑成 j
- 第 2 轮：dp[j] = 用硬币 1 和 2 凑成 j（但 2 只能在 1 后面添加）
强制顺序：硬币必须按 [1,2,5] 的顺序出现，不会出现 2 在 1 前面。
排列（外层金额）
dp[j] = 凑成 j 的排列数（任意硬币都可以作为最后一个）
- 凑成 3 时，可以是
[1]+ 凑成 2 的任意排列，也可以是[2]+ 凑成 1 的任意排列 - 不关心前面用了什么硬币，所以
[1,2]和[2,1]都算。
总结公式
| 目标 | 代码结构 |
|---|---|
| 组合数（本题） | for coin : for amount ✅ |
| 排列数 | for amount : for coin ❌ |
这就是为什么 LeetCode 518（零钱兑换 II）要求组合数，必须用外层循环硬币！
377. 组合总和 IV
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例
- nums = [1, 2, 3]
- target = 4
所有可能的组合为：(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3), (2, 1, 1), (2, 2), (3, 1)
请注意，顺序不同的序列被视作不同的组合。因此输出为 7。
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
// 先遍历背包，再遍历物品
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.length; j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
解题
本题与上一题目的区别在于本题在求排列数，所以只需要交换遍历顺序即可，先遍历背包，再遍历物品。
57. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多 m (1 <= m < n) 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述
输入共一行，包含两个正整数，分别表示 n, m。
输出描述
输出一个整数，表示爬到楼顶的方法数。
示例
- 输入：3 2
- 输出：3
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。此时你有三种方法可以爬到楼顶：
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
import java.util.Scanner;
class climbStairs {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m, n;
while (sc.hasNextInt()) {
// 从键盘输入参数，中间用空格隔开
n = sc.nextInt();
m = sc.nextInt();
// 求排列问题，先遍历背包再遍历物品
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
if (j - i >= 0) {
dp[j] += dp[j - i];
}
}
}
System.out.println(dp[n]);
}
}
}
解题
这是一个完全背包问题 + 排列问题。