377. 组合总和 Ⅳ

发表于 2026-01-04 分类于力扣阅读次数： Waline：本文字数： 861 阅读时长 ≈ 3 分钟

考点

线性DP
DP计算排列问题

思路

一、问题概述

给定一个由 正整数 组成的数组 nums 和一个目标值 target，要求计算：

使用 nums 中的元素（每个元素可重复使用），凑出和为 target 的方案数， 不同顺序视为不同方案。

例如：

nums = [1, 2]
target = 3

合法方案包括：

1 + 1 + 1
1 + 2
2 + 1

因此答案为 3。

二、状态定义（State Definition）

定义一维动态规划数组： \[ f[s] = \text{凑成总和为 } s \text{ 的方案数} \] 该定义具有以下特点：

状态只与“当前目标和”有关
不区分使用了哪些元素，而是从顺序角度计数
非常适合“顺序不同算不同方案”的 排列（permutation）问题

三、初始值（Initialization）

\[ f[0] = 1 \]

含义说明

凑出和为 0 的方式只有一种：什么都不选
这是一个计数 DP 中的关键基准状态
它保证了后续状态转移可以正确累加

如果没有这个初始条件，所有状态都将无法被推导出来。

四、状态转移方程（Transition）

对于任意 \(s \in [1, \text{target}]\)，有： \[ f[s] = \sum_{x \in nums,\; s \ge x} f[s - x] \]

转移逻辑解释

将“最后一步选了哪个数”作为划分方式
若最后一步选择了 x，那么前面的部分必须凑出 s - x
f[s - x] 的每一种方案，在末尾接上 x，都会形成一个新的合法方案

为什么这是“排列”而不是“组合”？

外层枚举的是 目标和 s
内层枚举的是 最后一步选择的元素 x
不同的“最后一步”顺序会被完整区分

五、循环结构与顺序

对应的循环结构为：

for s = 1 .. target:
    for each x in nums:
        if s >= x:
            f[s] += f[s - x]

该顺序是本题的关键：

外层是和，内层是元素
保证了 [1,2] 与 [2,1] 会被分别统计
若交换循环顺序，则会退化为“组合问题”，结果错误

六、整数溢出问题（非常重要）

1. 题目中的隐含条件

题目说明：

最终答案保证在 32 位有符号整数范围内

但需要注意：

并未保证中间 DP 状态不会溢出

在状态转移过程中，f[s] 可能会暂时变得非常大，随后在更大的 s 上被“抵消”或不再参与最终答案。

2. 有符号整数的风险

在 C++ 中：

int、long long 的溢出行为是 Undefined Behavior
一旦溢出，程序的行为将不再受语言标准保证
编译器可能基于“永不溢出”的假设进行激进优化，导致结果错误

3. 为什么使用 `unsigned` 是安全的？

unsigned int 的溢出行为是定义良好的
所有运算都在模 \(2^{32}\) 意义下进行
对于本题：
- 中间状态即使溢出，也只是在取模意义下循环
- 最终结果仍然能正确落在 int 范围内

因此，使用 unsigned 是一种工程上安全、符合题目语义的选择。

七、时间与空间复杂度

时间复杂度： \[ O(\text{target} \times |nums|) \]
空间复杂度： \[ O(\text{target}) \]

八、完整参考代码（已 AC）

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        unsigned f[1005];
        f[0] = 1;
        for (int i = 1; i <= target; ++i) {
            f[i] = 0;
            for (int x : nums) {
                if (i >= x)
                    f[i] += f[i - x];
            }
        }
        return f[target];
    }
};

考点

思路