动态规划实战：零钱兑换与爬楼梯中的组合数与排列数

• 组合数：外层循环硬币、内层循环金额。
• 排列数：外层循环金额、内层循环硬币。

例如 coins=[1,2]，amount=3：

• 只统计 (1,1,1) 和 (1,2)，不会把 (2,1) 算作另一种。

核心区别：组合 vs 排列

图示对比

假设 coins = [1, 2]，amount = 3

✅ 外层循环硬币（组合）

for (int coin : coins) { // 先固定硬币 1，再硬币 2
    for (int j = coin; j <= amount; j++) {
        dp[j] += dp[j - coin];
    }
}

执行过程：

结果 = 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];
    }
}

执行过程：

结果 = 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] 都算。

总结公式

这就是为什么 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]);
        }
    }
}

解题

这是一个完全背包问题 + 排列问题。