会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
要从互不相同的正整数里选数（可重复）凑成 target，顺序不同算不同方案。这是排列型完全背包，不是普通组合背包。
- 设 dp[t] 为凑出 t 的有序方案数，dp[0]=1。
- 外层枚举容量 t=1..target，内层枚举数组里的每个 x。若 t≥x，则 dp[t] 加上 dp[t−x]。
- 这样最后一个数可以是任意合法 x，前面那一段的排列已经算在 dp[t−x] 里，所以 1,2 和 2,1 会各计一次。
- 若改成外层枚举数字、内层枚举容量，就变成组合数，样例 1 会得到 4 而不是 7。
- 常见假解：当成组合（不管顺序）；每个数只能用一次；无法凑出时没输出 0。
