科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南基于 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}_i1$本题则把「隔 1 个」推广成「隔 $\textit{brainpower}_i$ 个」。因此凡是在打家劫舍上学到的「选/不选」建模方法都可以迁移过来——区别只在于跳过区间变长了。仓库中与该题配套的题解正文位于 2140.md同时 c.go 内保存了三种 Go 实现记忆化搜索、倒序递推、正序递推c_test.go 给出了两个样例用例供对照验证。解法一倒序 DP查表法/填表法填表法查表法适用于大多数 DP通过当前状态所依赖的状态来计算当前状态。设有 $n$ 个问题定义 $f[i]$ 表示解决区间 $[i,n-1]$ 内的问题可以获得的最高分数。倒序遍历问题列表对于第 $i$ 个问题我们有两种决策跳过或解决。跳过则有 $f[i]f[i1]$。解决则需要跳过后续 $\textit{brainpower}[i]$ 个问题。记 $ji\textit{brainpower}[i]1$则有$$ f[i] \begin{cases} \textit{point}[i]f[j],jn\ \textit{point}[i],j\ge n \end{cases} $$这两种决策取最大值$$ f[i] \max\left(f[i1],; \textit{point}[i] \begin{cases} f[j], jn \ 0, j\ge n \end{cases}\right) $$最后答案为 $f[0]$。代码实现上把 $f$ 数组开成 $n1$ 大小用 $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(vectorvectorint questions) { int n questions.size(); vectorlong 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, n1) for i : n - 1; i 0; i-- { q : questions[i] if j : i q[1] 1; j n { f[i] max(f[i1], q[0]f[j]) } else { f[i] max(f[i1], 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, n1) for i, q : range slices.Backward(questions) { j : min(iq[1]1, n) f[i] max(f[i1], f[j]int64(q[0])) } return f[0] }这里j : min(iq[1]1, n)与上面的if j n分支是等价的写法当跳过区间越过数组末尾时后面的得分就是 0即 $f[n]0$。复杂度分析时间复杂度$\mathcal{O}(n)$。空间复杂度$\mathcal{O}(n)$。解法二正序 DP刷表法另一种做法是刷表法用当前状态去更新当前状态所影响的状态。「倒序查表」天然契合本题因为状态转移是从后向前看$f[i]$ 依赖 $f[i1]$ 与 $f[j]$其中 $ji$。如果非要从左往右递推难点在于不好确定当前状态该从谁转移而来已知当前可以解决的问题是 $i$那么上一个可以解决的问题可能是很多个 $k$只要 $k\textit{brainpower}_k1i$ 或 $ki-1$并不好枚举。但对于这种「知道该去哪、不好知道该从哪来」的 DP可以用刷表法已知当前状态主动去更新它影响到的未来状态。定义 $f[i]$ 表示在可以解决问题 $i$ 时解决区间 $[0,i)$ 内的问题可以获得的最高分数。对于问题 $i$若跳过则可以更新 $f[i1]\max(f[i1],f[i])$。若不跳过记 $ji\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(vectorvectorint questions) { int n questions.size(); vectorlong 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, n1) for i, q : range questions { f[i1] max(f[i1], 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 补全了更完整的思考链条可帮助理解递推公式的来源寻找子问题讨论 $i$ 号问题选或不选两种选择都会把原问题变成规模更小的同型子问题因此可用递归建模$\textit{dfs}(i)$ 表示区间 $[i,n-1]$ 的最大得分。记忆化搜索由于递归中存在大量重复子问题用 memo 数组缓存结果注意 memo 初始值不能与合法结果冲突本题因 $\textit{point}_i0$用 0 作初始值安全。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(i1), dfs(iq[1]1)int64(q[0])) } return *p } return dfs(0) }如何思考循环顺序一个通用做法是盯着状态转移方程。要计算 $f[i]$必须先算好 $f[i1]$ 与 $f[i\textit{brainpower}_i1]$二者下标都大于 $i$因此解法一只需要 $i$从大到小枚举而刷表法是用 $f[i]$ 去更新 $f[i1]$、$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 分325若直接解决第 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背包、区间覆盖、带冷却的任务安排等中都通用。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 仓库 LeetCode 基础算法精讲题目汇总从双指针到树形 DP 的系统刷题路线codeforces go 仓库 LeetCode 基础算法精讲题目汇总从双指针到树形 DP 的系统刷题路线 本篇技术指南围绕 leetcode/README科学计算把数组当栈与双指针交换LeetCode 283 移动零的两种原地解法精讲codeforces-go 仓库题解把数组当栈与双指针交换LeetCode 283 移动零的两种原地解法精讲codeforces go 仓库题解 导读 本文围绕本仓库题解文档 leetcod科学计算codeforces-go 题解精讲二维网格迁移LeetCode 1260的映射展开与三次反转两种解法codeforces go 题解精讲二维网格迁移LeetCode 1260的映射展开与三次反转两种解法 本篇文章围绕算法竞赛模板库 codeforces科学计算上一篇一条命令把整个代码库变成 LLM 提示code2prompt 怎么用下一篇Langfuse 前端浏览器审查工作流面向 AI Agent 的用户可见变更验收与回归检查创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考