)
链接：377. 组合总和 Ⅳ - 力扣（LeetCode）
题解：
组合总和 IV
dp[i] 目标位i的组合组数是多少
dp[i] = dp[i-A0] + dp[i-A[1]] .. dp[1-A[n-1]]，枚举所有最后一个数字的可能
class Solution { public: int combinationSum4(vector<int>& nums, int target) { int len = nums.size(); if (len <= 0) { return 0; } vector<unsigned long long> dp(target + 1, 0); dp[0] = 1; for (int i = 0; i <= target; ++i) { for (int j = 0; j < nums.size(); ++ij) { if (i - nums[j] >= 0) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; } };外层循环决定“转移时被复用的dp值是完整的，还是只含部分物品的”。
本题dp[j]的语义是“和为j的排列数”，转移是：
cpp
dp[j] = Σ_{num ∈ nums, num ≤ j} dp[j - num]要让这个式子成立，右边每个dp[j - num]必须是完整的排列数（所有物品都能参与）。而它什么时候完整，取决于循环顺序。
1. 从“最后一步”看
一个和为j的排列，最后一步可以是任意num，前面部分是任意和为j - num的排列。
所以：
text
dp[j] = dp[j-1] + dp[j-2] + dp[j-3] + ... ↑ 最后一步是 1、2、3……
这里dp[j-num]必须是“任何物品都能用”的完整排列。
外层容量j：
cpp
for (int j = 1; j <= target; ++j) for (int num : nums) dp[j] += dp[j - num];
当你在第j层累加时，dp[j-num]已经在之前的轮次里把所有物品都累加完了，它是完整的。✓
外层物品num：
cpp
for (int num : nums) for (int j = num; j <= target; ++j) dp[j] += dp[j - num];
当你在处理物品num时，dp[j-num]只吸收了当前及之前处理过的物品，还没轮到后面的物品。它是“半成品”。用半成品去转移，就等于强制“前面的物品编号 ≤ 当前物品编号”
关键区别：零钱兑换求“最小值”，377 求“排列数”
一、为什么零钱兑换两个 for 颠倒都对
零钱兑换的目标是最少硬币数：
cpp
dp[i] = min(dp[i], dp[i - c] + 1);
min是可交换、可结合的运算。无论你先枚举硬币还是先枚举金额，只要保证每种硬币能无限次使用（内层金额正序），最终dp[i]都会收敛到同一个最小值。
顺序不同的方案，在“最小值”这个目标下是等价的。比如1+2和2+1都是 2 枚硬币，对min没有区别。
二、为什么 377 两个 for 颠倒就错了
377 的目标是排列数，dp[i] = sum(dp[i - c])，顺序不同算不同方案。
写法 A：外层金额，内层硬币（正确）
cpp
for (int i = 1; i <= target; ++i) { for (int c : nums) { if (i >= c) dp[i] += dp[i - c]; } }含义：对每个金额i，枚举“最后一个硬币是c”，前面的部分i - c可以是任意顺序的组合。
这样：
dp[1]从dp[0]来（最后一个硬币是 1）dp[2]从dp[1]（最后是 1）和dp[0]（最后是 2）来…
每个排列都会被统计一次，因为“最后一个硬币”唯一确定了排列的结尾。
写法 B：外层硬币，内层金额（错误，求的是组合数）
cpp
for (int c : nums) { for (int i = c; i <= target; ++i) { dp[i] += dp[i - c]; } }含义：先只用硬币 1，再加入硬币 2，再加入硬币 3……每种硬币按固定顺序“加入”。
这样统计出来的是组合数（顺序无关），因为硬币的加入顺序被固定了。{1,2}和{2,1}只会被算一次。
三、具体验证nums = [1,2,3], target = 4
写法 A（外层金额）
text
dp[0] = 1 dp[1] = dp[0] = 1 // {1} dp[2] = dp[1] + dp[0] = 2 // {1,1}, {2} dp[3] = dp[2] + dp[1] + dp[0] = 4 // {1,1,1}, {1,2}, {2,1}, {3} dp[4] = dp[3] + dp[2] + dp[1] = 4+2+1 = 7 // 7 个排列 ✅写法 B（外层硬币）
text
dp[0] = 1 硬币 1：dp[1]=1, dp[2]=1, dp[3]=1, dp[4]=1 硬币 2：dp[2]+=dp[0]=1 → 2, dp[3]+=dp[1]=1 → 2, dp[4]+=dp[2]=2 → 3 硬币 3：dp[3]+=dp[0]=1 → 3, dp[4]+=dp[1]=1 → 4 dp[4] = 4 // 只有 {1,1,1,1}, {1,1,2}, {1,3}, {2,2}，少了 3 个排列 ❌四、核心原因
| 问题 | 目标 | dp转移 | 两个 for 颠倒 |
|---|---|---|---|
| 零钱兑换 | 最少硬币数 | min | ✅ 都对 |
| 377 组合总和 IV | 排列数 | sum | ❌ 只有“外层金额、内层硬币”对 |
| 518 零钱兑换 II | 组合数 | sum | ❌ 只有“外层硬币、内层金额”对 |
关键规律：
求最值（min/max）：顺序无关，两种遍历都对。
求方案数：顺序有关。
排列数（顺序不同算不同）→ 外层金额，内层物品。
组合数（顺序不同算相同）→ 外层物品，内层金额。
五、记忆口诀
排列看“结尾”，组合看“物品”。
排列：固定最后一个元素，前面任意 →外层金额，内层物品。
组合：固定物品的加入顺序，逐个考虑 →外层物品，内层金额。
