LeetCode 2140 Solving Questions With Brainpower 全解从递归到自底向上 DP 的完整演进【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读Solving Questions With BrainpowerLeetCode 2140是动态规划专题中极具代表性的“带冷却期的序列决策”问题每道题目要么作答得分并跳过后续brainpower道题要么直接跳过进入下一题目标是最大化总分。本文以本仓库 articles/solving-questions-with-brainpower.md 为骨架完整讲解朴素递归DFS→ 自顶向下记忆化 DP → 自底向上迭代 DP三条解题路径并对照仓库内 C 实现、C 实现 与 Kotlin 实现 的源码细节帮助读者吃透重叠子问题、转移方程推导、索引跳跃与整数溢出等核心考点。读完后你将能独立完成此题并将这套“决策 冷却间隔”的 DP 建模方法迁移到同类序列选择问题。前置知识Prerequisites在动手写代码之前建议先确认自己具备以下四块基础能力它们对应着本题的四种解法演进路径递归Recursion把大问题拆成带基准条件base case的小子问题。本题中“从第i题开始能拿到的最大分”就是一个天然的自相似子问题。动态规划Dynamic Programming通过存储已计算结果来优化递归避免重复计算。记忆化Memoization把递归函数的中间结果缓存起来命中缓存直接返回。自底向上 DPBottom-Up DP不依赖递归栈从小到大本题是从右到左迭代填充 DP 表。本题非常适合用来验证这四块知识的递进关系先写出朴素的递归正确但指数级再叠加记忆化线性时间最后改写成无递归的迭代版本空间可控、无栈溢出风险。问题建模每道题的两个选择回顾题意questions是一个二维数组questions[i] [points_i, brainpower_i]表示第i题作答可获得points_i分但作答后必须跳过接下来的brainpower_i道题也可以选择不作答直接进入第i 1题。核心观察是处理到第i题时只有两种决策作答Solve获得points_i分下一次从i 1 brainpower_i题继续跳过Skip得 0 分下一次从i 1题继续。于是从位置i出发的最大得分可写成如下递推关系f(i) max( f(i 1), points_i f(i 1 brainpower_i) ) f(i) 0, 当 i n这个转移方程是整个题目的灵魂“当前题目跳过”与“当前题目作答并跳过后继若干题”二者取较大值。仓库 Kotlin 实现 中maxOf(questions[i][0] dfs(i 1 questions[i][1]), dfs(i 1))正是这一方程的直译。解法一朴素递归Recursion直觉Intuition每个位置有两种选择这天然形成一棵决策二叉树向左走代表跳过当前题向右走代表作答并跨越brainpower道题。我们的目标是在这棵树上找到得分最大的路径因此递归地枚举每条分支并返回最大值即可。算法步骤Algorithm定义从下标0开始的递归函数dfs(i)。基准条件若i超出数组长度i n返回0。每个下标计算两个分支跳过递归调用dfs(i 1)作答累加questions[i][0]再递归调用dfs(i 1 questions[i][1])。返回两者较大值。最终答案为dfs(0)。多语言实现Pythonclass Solution: def mostPoints(self, questions: List[List[int]]) - int: def dfs(i): if i len(questions): return 0 return max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dfs(0)Javapublic class Solution { public long mostPoints(int[][] questions) { return dfs(0, questions); } private long dfs(int i, int[][] questions) { if (i questions.length) return 0; return Math.max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); } }Cclass Solution { public: long long mostPoints(vectorvectorint questions) { return dfs(0, questions); } private: long long dfs(int i, vectorvectorint questions) { if (i questions.size()) return 0; return max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); } };JavaScriptclass Solution { /** * param {number[][]} questions * return {number} */ mostPoints(questions) { const dfs (i) { if (i questions.length) return 0; return Math.max( dfs(i 1), questions[i][0] dfs(i 1 questions[i][1]), ); }; return dfs(0); } }C#public class Solution { public long MostPoints(int[][] questions) { return Dfs(0, questions); } private long Dfs(int i, int[][] questions) { if (i questions.Length) return 0; return Math.Max(Dfs(i 1, questions), questions[i][0] Dfs(i 1 questions[i][1], questions)); } }Gofunc mostPoints(questions [][]int) int64 { var dfs func(i int) int64 dfs func(i int) int64 { if i len(questions) { return 0 } skip : dfs(i 1) take : int64(questions[i][0]) dfs(i 1 questions[i][1]) if skip take { return skip } return take } return dfs(0) }Kotlinclass Solution { fun mostPoints(questions: ArrayIntArray): Long { fun dfs(i: Int): Long { if (i questions.size) return 0 return maxOf(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) } return dfs(0) } }Swiftclass Solution { func mostPoints(_ questions: [[Int]]) - Int { func dfs(_ i: Int) - Int { if i questions.count { return 0 } return max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) } return dfs(0) } }Rustimpl Solution { pub fn most_points(questions: VecVeci32) - i64 { fn dfs(i: usize, questions: [Veci32]) - i64 { if i questions.len() { return 0; } let skip dfs(i 1, questions); let take questions[i][0] as i64 dfs(i 1 questions[i][1] as usize, questions); skip.max(take) } dfs(0, questions) } }复杂度分析时间复杂度$O(2^n)$——每个位置展开两个分支决策树规模呈指数增长空间复杂度$O(n)$——递归调用栈最大深度为n。朴素递归在n较大时会超时因为大量子问题被重复计算例如从不同路径反复进入同一个i。这正是下一步引入记忆化的动机。解法二自顶向下动态规划Top-Down DP / 记忆化直觉Intuition朴素递归存在重叠子问题dfs(i)可能从多个上层分支被反复调用。把每个下标的结果缓存进记忆化表后每个下标至多计算一次时间复杂度降为线性。算法步骤Algorithm建立记忆化字典或数组哈希表 / 定长数组均可。递归函数先查缓存命中则直接返回。未命中时计算“跳过”与“作答”两种决策的较大值。写入缓存后再返回。最终返回从下标0计算得到的结果。多语言实现Pythonclass Solution: def mostPoints(self, questions: List[List[int]]) - int: dp {} def dfs(i): if i len(questions): return 0 if i in dp: return dp[i] dp[i] max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dp[i] return dfs(0)Javapublic class Solution { private long[] dp; public long mostPoints(int[][] questions) { dp new long[questions.length]; return dfs(0, questions); } private long dfs(int i, int[][] questions) { if (i questions.length) return 0; if (dp[i] ! 0) return dp[i]; dp[i] Math.max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); return dp[i]; } }Cclass Solution { vectorlong long dp; public: long long mostPoints(vectorvectorint questions) { dp.assign(questions.size(), 0); return dfs(0, questions); } private: long long dfs(int i, vectorvectorint questions) { if (i questions.size()) return 0; if (dp[i] ! 0) return dp[i]; dp[i] max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); return dp[i]; } };JavaScriptclass Solution { /** * param {number[][]} questions * return {number} */ mostPoints(questions) { const dp new Array(questions.length).fill(-1); const dfs (i) { if (i questions.length) return 0; if (dp[i] ! -1) return dp[i]; dp[i] Math.max( dfs(i 1), questions[i][0] dfs(i 1 questions[i][1]), ); return dp[i]; }; return dfs(0); } }C#public class Solution { private long[] dp; public long MostPoints(int[][] questions) { dp new long[questions.Length]; return Dfs(0, questions); } private long Dfs(int i, int[][] questions) { if (i questions.Length) return 0; if (dp[i] ! 0) return dp[i]; dp[i] Math.Max(Dfs(i 1, questions), questions[i][0] Dfs(i 1 questions[i][1], questions)); return dp[i]; } }Gofunc mostPoints(questions [][]int) int64 { n : len(questions) dp : make([]int64, n) var dfs func(i int) int64 dfs func(i int) int64 { if i n { return 0 } if dp[i] ! 0 { return dp[i] } skip : dfs(i 1) take : int64(questions[i][0]) dfs(i 1 questions[i][1]) if skip take { dp[i] skip } else { dp[i] take } return dp[i] } return dfs(0) }Kotlinclass Solution { fun mostPoints(questions: ArrayIntArray): Long { val dp LongArray(questions.size) fun dfs(i: Int): Long { if (i questions.size) return 0 if (dp[i] ! 0L) return dp[i] dp[i] maxOf(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dp[i] } return dfs(0) } }Swiftclass Solution { func mostPoints(_ questions: [[Int]]) - Int { var dp Int func dfs(_ i: Int) - Int { if i questions.count { return 0 } if dp[i] ! -1 { return dp[i] } dp[i] max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dp[i] } return dfs(0) } }Rustimpl Solution { pub fn most_points(questions: VecVeci32) - i64 { let n questions.len(); let mut dp vec![-1i64; n]; fn dfs(i: usize, questions: [Veci32], dp: mut [i64]) - i64 { if i questions.len() { return 0; } if dp[i] ! -1 { return dp[i]; } let skip dfs(i 1, questions, dp); let take questions[i][0] as i64 dfs(i 1 questions[i][1] as usize, questions, dp); dp[i] skip.max(take); dp[i] } dfs(0, questions, mut dp) } }仓库 Kotlin 实现 中的第一版正是这种“DFS/Recursion Memoization”写法用LongArray(size) { -1L }初始化缓存memo[i] ! -1L作为是否已计算的哨兵判断与上述 Kotlin 代码互为印证。复杂度分析时间复杂度$O(n)$——每个下标至多被计算一次空间复杂度$O(n)$——记忆化数组加上递归栈深度。一个值得注意的实现细节在 Java/C/Go/C# 的上述写法中缓存数组初值为0且直接用dp[i] ! 0判断是否命中。由于本题得分恒为非负points_i 00作为“未计算”哨兵是安全的而 JavaScript/Swift/Rust 用-1作哨兵则更显式思路完全一致。理解这一差异有助于在实现其他 DP 题目时正确选择“未访问”标记值。解法三自底向上动态规划Bottom-Up DP直觉Intuition记忆化递归仍依赖调用栈且自顶向下本质上与迭代等价。改为从右向左迭代填充 DP 表处理i时所有大于i的位置i 1与i 1 brainpower_i的结果都已就绪因此可以直接套用转移方程。算法步骤Algorithm创建长度为n 1的dp数组并全部初始化为0多出的第n位充当哨兵表示“越过末尾”时的得分为 0。从最后一题向前遍历右到左。对下标i作答points_i dp[i 1 brainpower_i]若下标越界则取0用哨兵位dp[n] 0天然处理跳过dp[i 1]dp[i] max(作答, 跳过)。返回dp[0]即从第一题开始的最大得分。多语言实现Pythonclass Solution: def mostPoints(self, questions: List[List[int]]) - int: dp {} for i in range(len(questions) - 1, -1, -1): dp[i] max( questions[i][0] dp.get(i 1 questions[i][1], 0), dp.get(i 1, 0) ) return dp.get(0)Javapublic class Solution { public long mostPoints(int[][] questions) { int n questions.length; long[] dp new long[n 1]; for (int i n - 1; i 0; i--) { dp[i] Math.max( questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1] ); } return dp[0]; } }Cclass Solution { public: long long mostPoints(vectorvectorint questions) { int n questions.size(); vectorlong long dp(n 1, 0); for (int i n - 1; i 0; i--) { dp[i] max( (long long)questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1] ); } return dp[0]; } };JavaScriptclass Solution { /** * param {number[][]} questions * return {number} */ mostPoints(questions) { const n questions.length; const dp new Array(n 1).fill(0); for (let i n - 1; i 0; i--) { dp[i] Math.max( questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1], ); } return dp[0]; } }C#public class Solution { public long MostPoints(int[][] questions) { int n questions.Length; long[] dp new long[n 1]; for (int i n - 1; i 0; i--) { dp[i] Math.Max( questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1] ); } return dp[0]; } }Gofunc mostPoints(questions [][]int) int64 { n : len(questions) dp : make([]int64, n1) for i : n - 1; i 0; i-- { next : int64(0) if i 1 questions[i][1] n { next dp[i 1 questions[i][1]] } take : int64(questions[i][0]) next skip : dp[i 1] if take skip { dp[i] take } else { dp[i] skip } } return dp[0] }Kotlinclass Solution { fun mostPoints(questions: ArrayIntArray): Long { val n questions.size val dp LongArray(n 1) for (i in n - 1 downTo 0) { dp[i] maxOf( questions[i][0] if (i 1 questions[i][1] n) dp[i 1 questions[i][1]] else 0, dp[i 1] ) } return dp[0] } }Swiftclass Solution { func mostPoints(_ questions: [[Int]]) - Int { let n questions.count var dp Int for i in stride(from: n - 1, through: 0, by: -1) { let next i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0 dp[i] max(questions[i][0] next, dp[i 1]) } return dp[0] } }Rustimpl Solution { pub fn most_points(questions: VecVeci32) - i64 { let n questions.len(); let mut dp vec![0i64; n 1]; for i in (0..n).rev() { let jump i 1 questions[i][1] as usize; let next if jump n { dp[jump] } else { 0 }; dp[i] (questions[i][0] as i64 next).max(dp[i 1]); } dp[0] } }复杂度分析时间复杂度$O(n)$——单次线性扫描空间复杂度$O(n)$——DP 数组长度n 1。仓库源码对照三种工程化写法仓库中实际提交的解法与上文思想一致但呈现出三种不同的工程表达值得逐一对照Kotlin2140-solving-questions-with-brainpower.kt同时收录了“DFS Memoization”“数组 DP”“HashMap DP”三种写法。第三种用HashMapInt, Long代替定长数组借助dp[i 1] ?: 0L优雅处理越界代码更精简——这正好对应上文 Python 用字典dp.get(i, 0)的写法。C2140-solving-questions-with-brainpower.c分配n 1长度的long long*并malloc后手动清零再用(jump i 1) n ? ... : n三元表达式把越界索引收敛到哨兵位dp[n]最后free(dp)释放内存。这份实现演示了在无 GC 语言中如何用哨兵位替代“越界返回 0”的分支判断。Ccpp/2140-solving-questions-with-brainpower.cpp采用“从n - 2倒序 单独初始化dp[n-1]”的写法并把最大得分同步维护在ans中当k i questions[i][1] 1 n时直接以questions[i][0]与dp[i1]比较逻辑上与标准版等价可作为不同编码风格的参考。从仓库 README.md 的完成度表格可以看到本题目前仓库已提供 C、C、Kotlin 三份可运行实现其余语言位空缺读者可以参照上文的多语言代码自行补齐验证。常见陷阱Common Pitfalls陷阱一得分累加导致整数溢出单题得分与题目数量都可能较大跨多题累加后总分很容易超出 32 位int上限。因此 DP 数组与返回值必须使用 64 位类型Java/C# 用longC 用long longGo/Rust 用int64Kotlin 用Long。仓库 C、C、Kotlin 三份实现全部采用了 64 位类型long long/Long正是对这一陷阱的工程化规避注意 C 版本中(long long)questions[i][0]的显式强转也必不可少否则int相加仍可能先溢出再提升。陷阱二作答后的跳跃下标算错作答第i题后应跳到i 1 brainpower_i而不是i brainpower_i。多出的1表示“先越过当前这一题再跳过brainpower_i道题”。漏掉1会落到本应被跳过的题目上导致结果偏大或偏小是本题最经典的失误点。回顾所有版本的转移式i 1 questions[i][1]或i questions[i][1] 1两种写法等价但都包含这个关键1。陷阱三自底向上的遍历方向搞反自底向上版本必须从最后一题向第一题倒序遍历for i in range(n-1, -1, -1)或for (int i n-1; i 0; i--)。因为计算dp[i]时需要dp[i1]与dp[i1brainpower_i]均大于i只有倒序才能保证依赖值已就绪一旦正序遍历这些值还是初始值0答案必然错误。三种解法的横向对比与总结解法时间空间关键特征适用场景朴素递归$O(2^n)$$O(n)$结构直观存在大量重复计算仅用于理解问题结构无法通过大数据集自顶向下 DP记忆化$O(n)$$O(n)$保留递归思维缓存消除重叠子问题思维负担低适合先写对再优化自底向上 DP$O(n)$$O(n)$无递归栈迭代填表面试与工程首选避免栈溢出三条路径共享同一个转移方程f(i) max(f(i1), points_i f(i1brainpower_i))区别只在于计算顺序与结果存储方式。掌握从递归到记忆化再到迭代的演进逻辑比死记某一版代码更重要——这种“先暴力、再缓存、后改迭代”的套路可以原样迁移到带冷却期的打家劫舍House Robber II、任务调度Task Scheduling等一大批序列决策类 DP 题目上。建议读者对照本仓库 C、C、Kotlin 三份真实实现用多组含边界情况如brainpower_i 0、单题数组、全跳过最优等的用例逐一验证即可彻底吃透本题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 2140 Solving Questions With Brainpower 全解：从递归到自底向上 DP 的完整演进
LeetCode 2140 Solving Questions With Brainpower 全解从递归到自底向上 DP 的完整演进【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读Solving Questions With BrainpowerLeetCode 2140是动态规划专题中极具代表性的“带冷却期的序列决策”问题每道题目要么作答得分并跳过后续brainpower道题要么直接跳过进入下一题目标是最大化总分。本文以本仓库 articles/solving-questions-with-brainpower.md 为骨架完整讲解朴素递归DFS→ 自顶向下记忆化 DP → 自底向上迭代 DP三条解题路径并对照仓库内 C 实现、C 实现 与 Kotlin 实现 的源码细节帮助读者吃透重叠子问题、转移方程推导、索引跳跃与整数溢出等核心考点。读完后你将能独立完成此题并将这套“决策 冷却间隔”的 DP 建模方法迁移到同类序列选择问题。前置知识Prerequisites在动手写代码之前建议先确认自己具备以下四块基础能力它们对应着本题的四种解法演进路径递归Recursion把大问题拆成带基准条件base case的小子问题。本题中“从第i题开始能拿到的最大分”就是一个天然的自相似子问题。动态规划Dynamic Programming通过存储已计算结果来优化递归避免重复计算。记忆化Memoization把递归函数的中间结果缓存起来命中缓存直接返回。自底向上 DPBottom-Up DP不依赖递归栈从小到大本题是从右到左迭代填充 DP 表。本题非常适合用来验证这四块知识的递进关系先写出朴素的递归正确但指数级再叠加记忆化线性时间最后改写成无递归的迭代版本空间可控、无栈溢出风险。问题建模每道题的两个选择回顾题意questions是一个二维数组questions[i] [points_i, brainpower_i]表示第i题作答可获得points_i分但作答后必须跳过接下来的brainpower_i道题也可以选择不作答直接进入第i 1题。核心观察是处理到第i题时只有两种决策作答Solve获得points_i分下一次从i 1 brainpower_i题继续跳过Skip得 0 分下一次从i 1题继续。于是从位置i出发的最大得分可写成如下递推关系f(i) max( f(i 1), points_i f(i 1 brainpower_i) ) f(i) 0, 当 i n这个转移方程是整个题目的灵魂“当前题目跳过”与“当前题目作答并跳过后继若干题”二者取较大值。仓库 Kotlin 实现 中maxOf(questions[i][0] dfs(i 1 questions[i][1]), dfs(i 1))正是这一方程的直译。解法一朴素递归Recursion直觉Intuition每个位置有两种选择这天然形成一棵决策二叉树向左走代表跳过当前题向右走代表作答并跨越brainpower道题。我们的目标是在这棵树上找到得分最大的路径因此递归地枚举每条分支并返回最大值即可。算法步骤Algorithm定义从下标0开始的递归函数dfs(i)。基准条件若i超出数组长度i n返回0。每个下标计算两个分支跳过递归调用dfs(i 1)作答累加questions[i][0]再递归调用dfs(i 1 questions[i][1])。返回两者较大值。最终答案为dfs(0)。多语言实现Pythonclass Solution: def mostPoints(self, questions: List[List[int]]) - int: def dfs(i): if i len(questions): return 0 return max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dfs(0)Javapublic class Solution { public long mostPoints(int[][] questions) { return dfs(0, questions); } private long dfs(int i, int[][] questions) { if (i questions.length) return 0; return Math.max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); } }Cclass Solution { public: long long mostPoints(vectorvectorint questions) { return dfs(0, questions); } private: long long dfs(int i, vectorvectorint questions) { if (i questions.size()) return 0; return max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); } };JavaScriptclass Solution { /** * param {number[][]} questions * return {number} */ mostPoints(questions) { const dfs (i) { if (i questions.length) return 0; return Math.max( dfs(i 1), questions[i][0] dfs(i 1 questions[i][1]), ); }; return dfs(0); } }C#public class Solution { public long MostPoints(int[][] questions) { return Dfs(0, questions); } private long Dfs(int i, int[][] questions) { if (i questions.Length) return 0; return Math.Max(Dfs(i 1, questions), questions[i][0] Dfs(i 1 questions[i][1], questions)); } }Gofunc mostPoints(questions [][]int) int64 { var dfs func(i int) int64 dfs func(i int) int64 { if i len(questions) { return 0 } skip : dfs(i 1) take : int64(questions[i][0]) dfs(i 1 questions[i][1]) if skip take { return skip } return take } return dfs(0) }Kotlinclass Solution { fun mostPoints(questions: ArrayIntArray): Long { fun dfs(i: Int): Long { if (i questions.size) return 0 return maxOf(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) } return dfs(0) } }Swiftclass Solution { func mostPoints(_ questions: [[Int]]) - Int { func dfs(_ i: Int) - Int { if i questions.count { return 0 } return max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) } return dfs(0) } }Rustimpl Solution { pub fn most_points(questions: VecVeci32) - i64 { fn dfs(i: usize, questions: [Veci32]) - i64 { if i questions.len() { return 0; } let skip dfs(i 1, questions); let take questions[i][0] as i64 dfs(i 1 questions[i][1] as usize, questions); skip.max(take) } dfs(0, questions) } }复杂度分析时间复杂度$O(2^n)$——每个位置展开两个分支决策树规模呈指数增长空间复杂度$O(n)$——递归调用栈最大深度为n。朴素递归在n较大时会超时因为大量子问题被重复计算例如从不同路径反复进入同一个i。这正是下一步引入记忆化的动机。解法二自顶向下动态规划Top-Down DP / 记忆化直觉Intuition朴素递归存在重叠子问题dfs(i)可能从多个上层分支被反复调用。把每个下标的结果缓存进记忆化表后每个下标至多计算一次时间复杂度降为线性。算法步骤Algorithm建立记忆化字典或数组哈希表 / 定长数组均可。递归函数先查缓存命中则直接返回。未命中时计算“跳过”与“作答”两种决策的较大值。写入缓存后再返回。最终返回从下标0计算得到的结果。多语言实现Pythonclass Solution: def mostPoints(self, questions: List[List[int]]) - int: dp {} def dfs(i): if i len(questions): return 0 if i in dp: return dp[i] dp[i] max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dp[i] return dfs(0)Javapublic class Solution { private long[] dp; public long mostPoints(int[][] questions) { dp new long[questions.length]; return dfs(0, questions); } private long dfs(int i, int[][] questions) { if (i questions.length) return 0; if (dp[i] ! 0) return dp[i]; dp[i] Math.max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); return dp[i]; } }Cclass Solution { vectorlong long dp; public: long long mostPoints(vectorvectorint questions) { dp.assign(questions.size(), 0); return dfs(0, questions); } private: long long dfs(int i, vectorvectorint questions) { if (i questions.size()) return 0; if (dp[i] ! 0) return dp[i]; dp[i] max(dfs(i 1, questions), questions[i][0] dfs(i 1 questions[i][1], questions)); return dp[i]; } };JavaScriptclass Solution { /** * param {number[][]} questions * return {number} */ mostPoints(questions) { const dp new Array(questions.length).fill(-1); const dfs (i) { if (i questions.length) return 0; if (dp[i] ! -1) return dp[i]; dp[i] Math.max( dfs(i 1), questions[i][0] dfs(i 1 questions[i][1]), ); return dp[i]; }; return dfs(0); } }C#public class Solution { private long[] dp; public long MostPoints(int[][] questions) { dp new long[questions.Length]; return Dfs(0, questions); } private long Dfs(int i, int[][] questions) { if (i questions.Length) return 0; if (dp[i] ! 0) return dp[i]; dp[i] Math.Max(Dfs(i 1, questions), questions[i][0] Dfs(i 1 questions[i][1], questions)); return dp[i]; } }Gofunc mostPoints(questions [][]int) int64 { n : len(questions) dp : make([]int64, n) var dfs func(i int) int64 dfs func(i int) int64 { if i n { return 0 } if dp[i] ! 0 { return dp[i] } skip : dfs(i 1) take : int64(questions[i][0]) dfs(i 1 questions[i][1]) if skip take { dp[i] skip } else { dp[i] take } return dp[i] } return dfs(0) }Kotlinclass Solution { fun mostPoints(questions: ArrayIntArray): Long { val dp LongArray(questions.size) fun dfs(i: Int): Long { if (i questions.size) return 0 if (dp[i] ! 0L) return dp[i] dp[i] maxOf(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dp[i] } return dfs(0) } }Swiftclass Solution { func mostPoints(_ questions: [[Int]]) - Int { var dp Int func dfs(_ i: Int) - Int { if i questions.count { return 0 } if dp[i] ! -1 { return dp[i] } dp[i] max(dfs(i 1), questions[i][0] dfs(i 1 questions[i][1])) return dp[i] } return dfs(0) } }Rustimpl Solution { pub fn most_points(questions: VecVeci32) - i64 { let n questions.len(); let mut dp vec![-1i64; n]; fn dfs(i: usize, questions: [Veci32], dp: mut [i64]) - i64 { if i questions.len() { return 0; } if dp[i] ! -1 { return dp[i]; } let skip dfs(i 1, questions, dp); let take questions[i][0] as i64 dfs(i 1 questions[i][1] as usize, questions, dp); dp[i] skip.max(take); dp[i] } dfs(0, questions, mut dp) } }仓库 Kotlin 实现 中的第一版正是这种“DFS/Recursion Memoization”写法用LongArray(size) { -1L }初始化缓存memo[i] ! -1L作为是否已计算的哨兵判断与上述 Kotlin 代码互为印证。复杂度分析时间复杂度$O(n)$——每个下标至多被计算一次空间复杂度$O(n)$——记忆化数组加上递归栈深度。一个值得注意的实现细节在 Java/C/Go/C# 的上述写法中缓存数组初值为0且直接用dp[i] ! 0判断是否命中。由于本题得分恒为非负points_i 00作为“未计算”哨兵是安全的而 JavaScript/Swift/Rust 用-1作哨兵则更显式思路完全一致。理解这一差异有助于在实现其他 DP 题目时正确选择“未访问”标记值。解法三自底向上动态规划Bottom-Up DP直觉Intuition记忆化递归仍依赖调用栈且自顶向下本质上与迭代等价。改为从右向左迭代填充 DP 表处理i时所有大于i的位置i 1与i 1 brainpower_i的结果都已就绪因此可以直接套用转移方程。算法步骤Algorithm创建长度为n 1的dp数组并全部初始化为0多出的第n位充当哨兵表示“越过末尾”时的得分为 0。从最后一题向前遍历右到左。对下标i作答points_i dp[i 1 brainpower_i]若下标越界则取0用哨兵位dp[n] 0天然处理跳过dp[i 1]dp[i] max(作答, 跳过)。返回dp[0]即从第一题开始的最大得分。多语言实现Pythonclass Solution: def mostPoints(self, questions: List[List[int]]) - int: dp {} for i in range(len(questions) - 1, -1, -1): dp[i] max( questions[i][0] dp.get(i 1 questions[i][1], 0), dp.get(i 1, 0) ) return dp.get(0)Javapublic class Solution { public long mostPoints(int[][] questions) { int n questions.length; long[] dp new long[n 1]; for (int i n - 1; i 0; i--) { dp[i] Math.max( questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1] ); } return dp[0]; } }Cclass Solution { public: long long mostPoints(vectorvectorint questions) { int n questions.size(); vectorlong long dp(n 1, 0); for (int i n - 1; i 0; i--) { dp[i] max( (long long)questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1] ); } return dp[0]; } };JavaScriptclass Solution { /** * param {number[][]} questions * return {number} */ mostPoints(questions) { const n questions.length; const dp new Array(n 1).fill(0); for (let i n - 1; i 0; i--) { dp[i] Math.max( questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1], ); } return dp[0]; } }C#public class Solution { public long MostPoints(int[][] questions) { int n questions.Length; long[] dp new long[n 1]; for (int i n - 1; i 0; i--) { dp[i] Math.Max( questions[i][0] (i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0), dp[i 1] ); } return dp[0]; } }Gofunc mostPoints(questions [][]int) int64 { n : len(questions) dp : make([]int64, n1) for i : n - 1; i 0; i-- { next : int64(0) if i 1 questions[i][1] n { next dp[i 1 questions[i][1]] } take : int64(questions[i][0]) next skip : dp[i 1] if take skip { dp[i] take } else { dp[i] skip } } return dp[0] }Kotlinclass Solution { fun mostPoints(questions: ArrayIntArray): Long { val n questions.size val dp LongArray(n 1) for (i in n - 1 downTo 0) { dp[i] maxOf( questions[i][0] if (i 1 questions[i][1] n) dp[i 1 questions[i][1]] else 0, dp[i 1] ) } return dp[0] } }Swiftclass Solution { func mostPoints(_ questions: [[Int]]) - Int { let n questions.count var dp Int for i in stride(from: n - 1, through: 0, by: -1) { let next i 1 questions[i][1] n ? dp[i 1 questions[i][1]] : 0 dp[i] max(questions[i][0] next, dp[i 1]) } return dp[0] } }Rustimpl Solution { pub fn most_points(questions: VecVeci32) - i64 { let n questions.len(); let mut dp vec![0i64; n 1]; for i in (0..n).rev() { let jump i 1 questions[i][1] as usize; let next if jump n { dp[jump] } else { 0 }; dp[i] (questions[i][0] as i64 next).max(dp[i 1]); } dp[0] } }复杂度分析时间复杂度$O(n)$——单次线性扫描空间复杂度$O(n)$——DP 数组长度n 1。仓库源码对照三种工程化写法仓库中实际提交的解法与上文思想一致但呈现出三种不同的工程表达值得逐一对照Kotlin2140-solving-questions-with-brainpower.kt同时收录了“DFS Memoization”“数组 DP”“HashMap DP”三种写法。第三种用HashMapInt, Long代替定长数组借助dp[i 1] ?: 0L优雅处理越界代码更精简——这正好对应上文 Python 用字典dp.get(i, 0)的写法。C2140-solving-questions-with-brainpower.c分配n 1长度的long long*并malloc后手动清零再用(jump i 1) n ? ... : n三元表达式把越界索引收敛到哨兵位dp[n]最后free(dp)释放内存。这份实现演示了在无 GC 语言中如何用哨兵位替代“越界返回 0”的分支判断。Ccpp/2140-solving-questions-with-brainpower.cpp采用“从n - 2倒序 单独初始化dp[n-1]”的写法并把最大得分同步维护在ans中当k i questions[i][1] 1 n时直接以questions[i][0]与dp[i1]比较逻辑上与标准版等价可作为不同编码风格的参考。从仓库 README.md 的完成度表格可以看到本题目前仓库已提供 C、C、Kotlin 三份可运行实现其余语言位空缺读者可以参照上文的多语言代码自行补齐验证。常见陷阱Common Pitfalls陷阱一得分累加导致整数溢出单题得分与题目数量都可能较大跨多题累加后总分很容易超出 32 位int上限。因此 DP 数组与返回值必须使用 64 位类型Java/C# 用longC 用long longGo/Rust 用int64Kotlin 用Long。仓库 C、C、Kotlin 三份实现全部采用了 64 位类型long long/Long正是对这一陷阱的工程化规避注意 C 版本中(long long)questions[i][0]的显式强转也必不可少否则int相加仍可能先溢出再提升。陷阱二作答后的跳跃下标算错作答第i题后应跳到i 1 brainpower_i而不是i brainpower_i。多出的1表示“先越过当前这一题再跳过brainpower_i道题”。漏掉1会落到本应被跳过的题目上导致结果偏大或偏小是本题最经典的失误点。回顾所有版本的转移式i 1 questions[i][1]或i questions[i][1] 1两种写法等价但都包含这个关键1。陷阱三自底向上的遍历方向搞反自底向上版本必须从最后一题向第一题倒序遍历for i in range(n-1, -1, -1)或for (int i n-1; i 0; i--)。因为计算dp[i]时需要dp[i1]与dp[i1brainpower_i]均大于i只有倒序才能保证依赖值已就绪一旦正序遍历这些值还是初始值0答案必然错误。三种解法的横向对比与总结解法时间空间关键特征适用场景朴素递归$O(2^n)$$O(n)$结构直观存在大量重复计算仅用于理解问题结构无法通过大数据集自顶向下 DP记忆化$O(n)$$O(n)$保留递归思维缓存消除重叠子问题思维负担低适合先写对再优化自底向上 DP$O(n)$$O(n)$无递归栈迭代填表面试与工程首选避免栈溢出三条路径共享同一个转移方程f(i) max(f(i1), points_i f(i1brainpower_i))区别只在于计算顺序与结果存储方式。掌握从递归到记忆化再到迭代的演进逻辑比死记某一版代码更重要——这种“先暴力、再缓存、后改迭代”的套路可以原样迁移到带冷却期的打家劫舍House Robber II、任务调度Task Scheduling等一大批序列决策类 DP 题目上。建议读者对照本仓库 C、C、Kotlin 三份真实实现用多组含边界情况如brainpower_i 0、单题数组、全跳过最优等的用例逐一验证即可彻底吃透本题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考