企业官网建设流程全解析

• 科学计算

本篇技术指南基于 old.md（灵茶山艾府在 codeforces-go 仓库中维护的 LeetCode 题解笔记）展开，深入剖析 LeetCode 2140「解决智力问题」（Solving Questions With Brainpower，第 276 场周赛 C 题）的动态规划解法。该题是典型的一维序列决策型 DP，是「打家劫舍」的变形，适合用来打通「倒序查表」与「正序刷表」两种递推范式。读完本文，你将掌握：如何通过选/不选两种决策建立状态转移方程、何时该倒序枚举、何时该正序枚举，以及如何用 O(n) 时间与 O(n) 空间完成求解，并能对照仓库中的 Go 实现与测试用例自行验证。

题目与建模：带冷却期的选或不选

给定 $n$ 个问题，第 $i$ 个问题有两个属性：得分 $\textit{point}[i]$ 与冷却/跳过期 $\textit{brainpower}[i]$。若解决第 $i$ 个问题，可以获得 $\textit{point}[i]$ 分，但接下来 $\textit{brainpower}[i]$ 个问题都不能解决；若跳过，则可继续考虑下一个问题。目标是求出在全部 $n$ 个问题上能获得的最大分数。

本题其实是 198. 打家劫舍 的变形：打家劫舍要求选了一间房后下一间不能选，等价于 $\textit{brainpower}_i=1$；本题则把「隔 1 个」推广成「隔 $\textit{brainpower}_i$ 个」。因此，凡是在打家劫舍上学到的「选/不选」建模方法，都可以迁移过来——区别只在于跳过区间变长了。

仓库中与该题配套的题解正文位于 2140.md，同时 c.go 内保存了三种 Go 实现（记忆化搜索、倒序递推、正序递推），c_test.go 给出了两个样例用例，供对照验证。

解法一：倒序 DP（查表法/填表法）

填表法（查表法）适用于大多数 DP：通过当前状态所依赖的状态，来计算当前状态。

设有 $n$ 个问题，定义 $f[i]$ 表示解决区间 $[i,n-1]$ 内的问题可以获得的最高分数。

倒序遍历问题列表，对于第 $i$ 个问题，我们有两种决策：跳过或解决。

• 跳过，则有 $f[i]=f[i+1]$。
• 解决，则需要跳过后续 $\textit{brainpower}[i]$ 个问题。记 $j=i+\textit{brainpower}[i]+1$，则有

$$ f[i] = \begin{cases} \textit{point}[i]+f[j],&j<n\ \textit{point}[i],&j\ge n \end{cases} $$

这两种决策取最大值：

$$ f[i] = \max\left(f[i+1],; \textit{point}[i] + \begin{cases} f[j], & j<n \ 0, & j\ge n \end{cases}\right) $$

最后答案为 $f[0]$。代码实现上，把 $f$ 数组开成 $n+1$ 大小，用 $f[n]=0$ 充当递归边界（区间为空，得分为 0），即可统一处理 $j\ge n$ 的分支。

class Solution: def mostPoints(self, questions: List[List[int]]) -> int: n = len(questions) f = [0] * (n + 1) for i in range(n - 1, -1, -1): point, brainpower = questions[i] j = i + brainpower + 1 f[i] = max(f[i + 1], point + (f[j] if j < n else 0)) return f[0]

class Solution { public long mostPoints(int[][] questions) { int n = questions.length; long[] f = new long[n + 1]; for (int i = n - 1; i >= 0; i--) { int[] q = questions[i]; int j = i + q[1] + 1; f[i] = Math.max(f[i + 1], q[0] + (j < n ? f[j] : 0)); } return f[0]; } }

class Solution { public: long long mostPoints(vector<vector<int>>& questions) { int n = questions.size(); vector<long long> f(n + 1); for (int i = n - 1; i >= 0; i--) { auto& q = questions[i]; int j = i + q[1] + 1; f[i] = max(f[i + 1], q[0] + (j < n ? f[j] : 0)); } return f[0]; } };

func mostPoints(questions [][]int) int64 { n := len(questions) f := make([]int, n+1) for i := n - 1; i >= 0; i-- { q := questions[i] if j := i + q[1] + 1; j < n { f[i] = max(f[i+1], q[0]+f[j]) } else { f[i] = max(f[i+1], q[0]) } } return int64(f[0]) }

这段 Go 代码与仓库 c.go 中的mostPoints2完全对应，后者利用 Go 1.23 的slices.Backward从右往左遍历，并把越界状态统一压到哨兵位置 $n$：

func mostPoints2(questions [][]int) int64 { n := len(questions) f := make([]int64, n+1) for i, q := range slices.Backward(questions) { j := min(i+q[1]+1, n) f[i] = max(f[i+1], f[j]+int64(q[0])) } return f[0] }

这里j := min(i+q[1]+1, n)与上面的if j < n分支是等价的写法：当跳过区间越过数组末尾时，后面的得分就是 0，即 $f[n]=0$。

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)$。

解法二：正序 DP（刷表法）

另一种做法是刷表法：用当前状态，去更新当前状态所影响的状态。

「倒序查表」天然契合本题，因为状态转移是从后向前看（$f[i]$ 依赖 $f[i+1]$ 与 $f[j]$，其中 $j>i$）。如果非要从左往右递推，难点在于不好确定当前状态该从谁转移而来：已知当前可以解决的问题是 $i$，那么上一个可以解决的问题可能是很多个 $k$（只要 $k+\textit{brainpower}_k+1=i$ 或 $k=i-1$），并不好枚举。

但对于这种「知道该去哪、不好知道该从哪来」的 DP，可以用刷表法：已知当前状态，主动去更新它影响到的未来状态。

定义 $f[i]$ 表示在可以解决问题 $i$ 时，解决区间 $[0,i)$ 内的问题可以获得的最高分数。

对于问题 $i$，若跳过，则可以更新 $f[i+1]=\max(f[i+1],f[i])$。

若不跳过，记 $j=i+\textit{brainpower}[i]+1$，则可以更新 $f[j]=\max(f[j],f[i]+\textit{point}[i])$。

对于 $j\ge n$ 的情况，为了简化代码逻辑，我们可以将其更新到 $f[n]$ 中（把 $n$ 当作一个虚拟的结束问题）。

初始值 $f[0]=0$（区间 $[0,-1]$ 为空，没有问题，得分为 0），最后答案为 $f[n]$。

class Solution: def mostPoints(self, questions: List[List[int]]) -> int: n = len(questions) f = [0] * (n + 1) for i, (point, brainpower) in enumerate(questions): f[i + 1] = max(f[i + 1], f[i]) j = min(i + brainpower + 1, n) f[j] = max(f[j], f[i] + point) return f[n]

class Solution { public long mostPoints(int[][] questions) { int n = questions.length; long[] f = new long[n + 1]; for (int i = 0; i < n; i++) { f[i + 1] = Math.max(f[i + 1], f[i]); int[] q = questions[i]; int j = Math.min(i + q[1] + 1, n); f[j] = Math.max(f[j], f[i] + q[0]); } return f[n]; } }

class Solution { public: long long mostPoints(vector<vector<int>>& questions) { int n = questions.size(); vector<long long> f(n + 1); for (int i = 0; i < n; i++) { f[i + 1] = max(f[i + 1], f[i]); auto& q = questions[i]; int j = min(i + q[1] + 1, n); f[j] = max(f[j], f[i] + q[0]); } return f[n]; } };

func mostPoints(questions [][]int) int64 { n := len(questions) f := make([]int, n+1) for i, q := range questions { f[i+1] = max(f[i+1], f[i]) j := i + q[1] + 1 if j > n { j = n } f[j] = max(f[j], f[i]+q[0]) } return int64(f[n]) }

这段实现正是仓库 c.go 中的主函数mostPoints（该函数上方注释github.com/EndlessCheng/codeforces-go标明了出处），它把越界更新统一收敛到哨兵下标 $n$，实现非常简洁。

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)$。

从递归到递推：两种写法的思考路径（仓库补充视角）

虽然 old.md 直接给出两种递推写法，但仓库配套的 2140.md 补全了更完整的思考链条，可帮助理解递推公式的来源：

1. 寻找子问题：讨论 $i$ 号问题选或不选，两种选择都会把原问题变成规模更小的同型子问题，因此可用递归建模：$\textit{dfs}(i)$ 表示区间 $[i,n-1]$ 的最大得分。
2. 记忆化搜索：由于递归中存在大量重复子问题，用 memo 数组缓存结果；注意 memo 初始值不能与合法结果冲突（本题因 $\textit{point}_i>0$，用 0 作初始值安全）。
3. 1:1 翻译成递推：去掉递归中的「递」、只保留「归」，即为解法一的倒序填表。

仓库 c.go 中的mostPoints1正是记忆化搜索版本，可逐行对照：

func mostPoints1(questions [][]int) int64 { n := len(questions) memo := make([]int64, n) var dfs func(int) int64 dfs = func(i int) int64 { if i >= n { return 0 } p := &memo[i] if *p == 0 { // 未计算过才进入递归 q := questions[i] *p = max(dfs(i+1), dfs(i+q[1]+1)+int64(q[0])) } return *p } return dfs(0) }

如何思考循环顺序？

一个通用做法是：盯着状态转移方程。要计算 $f[i]$，必须先算好 $f[i+1]$ 与 $f[i+\textit{brainpower}_i+1]$（二者下标都大于 $i$），因此解法一只需要 $i$从大到小枚举；而刷表法是用 $f[i]$ 去更新 $f[i+1]$、$f[j]$（下标均大于 $i$），所以从前往后扫一遍即可，每个状态都恰好被推进一次。

测试用例与仓库验证

仓库 c_test.go 由copypasta/template/leetcode/generator_test.go生成，通过testutil.RunLeetCodeFuncWithExamples驱动mostPoints跑样例：

• 输入[[3,2],[4,3],[4,4],[2,5]]，期望输出5：最优解是只解决第 0 题拿 3 分、跳过后续 2 题，然后解决第 3 题再拿 2 分（3+2=5）；若直接解决第 1、2 题会触发较长的冷却，反而得不偿失。
• 输入[[1,1],[2,2],[3,3],[4,4],[5,5]]，期望输出7：最优解为第 0 题（1 分）+ 第 2 题（3 分）+ 第 4 题（5 分）= 9 分上限需要验证冷却约束，实际期望是 7，说明间隔限制确实生效。

这两个样例分别覆盖了「隔多个才能再选」与「brainpower 递增、交错选择」的情形。读者可复制 c.go 中任一实现（mostPoints/mostPoints2/mostPoints1），在本地go test下运行验证；三类实现复杂度一致，可作为一维选/不选 DP 的模板代码使用。

延伸与分类

本题属于「一维 DP」范畴，在仓库维护的完整题解索引 SOLUTIONS.md 中，动态规划一列收录了大量同类递推题型（如 70. 爬楼梯、746. 使用最小花费爬楼梯、198. 打家劫舍 等），思路均为「找子问题 → 状态定义 → 转移方程 → 循环顺序」。原文档末尾附带的滑动窗口、二分、单调栈、网格图、位运算、图论、动态规划、数据结构、数学、贪心、链表二叉树、字符串等分类题单，可参见 2140.md 中的「分类题单」一节以及仓库 SOLUTIONS.md 按难度与知识点组织的完整列表，作为系统刷题路线参考。

掌握本题的价值在于：它把「打家劫舍」式的选/不选模型推广为「选后跳过 k 项」的更一般情形，且同时示范了查表法与刷表法两种递推视角——前者追问「当前状态依赖谁」，后者追问「当前状态能影响谁」。这两种思维在任何一维决策型 DP（背包、区间覆盖、带冷却的任务安排等）中都通用。

• 科学计算