§1

题目描述

给定 questions[i] = [points, brainpower]。解决第 i 题得 points 分,但必须跳过紧随其后的 brainpower 道题;也可以直接跳过第 i 题。求能拿到的最大总分。

输入 = questions=[[3,2],[4,3],[4,4],[2,5]]　输出 = 5(做第 0 题和第 3 题)

输入 = questions=[[1,1],[2,2],[3,3],[4,4],[5,5]]　输出 = 7

§2

思路解析

一句话答案：LeetCode 2140 解决智力题：做第 i 题拿 points 分、但后面 brainpower 道题作废，问最高总分。倒序一维 DP，dp[i] 取做题与跳过的较大值，从最后一题往前填，时间 O(n)、空间 O(n)。

解决智力题到底在选什么

questions 的每一项是 [points, brainpower]：做第 i 题拿 points 分，代价是紧随的 brainpower 道题全部作废；也可以不做、直接看下一题。问总分最多是多少。例子一 [[3,2],[4,3],[4,4],[2,5]]，做第 0 题和第 3 题共 5 分最优。

为什么不能把每题做不做全试一遍

每道题都是做与不做两个分支，n 道题就是 2ⁿ 种组合，n 到 10⁵ 根本数不完。大量组合的后半段还重复：不管前面怎么选，只要都落到第 3 题，从第 3 题起的最高分都一样，硬枚举重算无数遍，存一次就够。

dp[i] 为什么要从最后一题倒着填

这就是动态规划（DP，把「从第 i 题起最多能拿几分」的答案存进表里，后面直接取）。定义 dp[i]：站在第 i 题、后面随意选，能拿到的最高分，答案是 dp[0]。

这张表得倒着填。原因在依赖方向：第 i 题做不做划算，取决于更靠后的题，dp[i] 要用靠右的格子，右边不先算左边没数可取。表末补一格 dp[n]=0 当哨兵（越过最后一题一分也拿不到），最右边的题才有格子可接。

做完第 i 题，下一个落点怎么数才不越界

每格两条路。不做第 i 题：顺延到下一题，得 dp[i+1]。做第 i 题：拿下 points，其后 brainpower 道全作废，下一道是第 i+brainpower+1 题，得 points+dp[i+brainpower+1]。两路取大即 dp[i]，这条规则叫转移（由已填好的格子推出当前格）。

落点最容易数错：跳过 brainpower 道，自己这格也要迈过去，所以加 brainpower 再加 1；它可能冲出表外，参考代码用 nxt = min(n, i+brainpower+1) 夹回哨兵，冲多远都算 0 分。

题面四道题，倒着一路填到 dp[0]=5

先摆哨兵 dp[4]=0。第 3 题 [2,5]：做它落点 min(4, 3+5+1)=4，得 2+dp[4]=2，不做得 0，dp[3]=2。第 2 题 [4,4]：落点夹到 4，做得 4+0=4，不做得 2，dp[2]=4。第 1 题 [4,3]：落点也夹到 4，做得 4，不做得 dp[2]=4，打平，dp[1]=4。

第 0 题 [3,2]：落点 min(4, 0+2+1)=3，做得 3+dp[3]=5，不做得 dp[1]=4，取大 dp[0]=5。正是题面的 5：做第 0 题、作废第 1、2 题，落到第 3 题收 2 分。

nxt 少加 1，样例一为什么会算成 7 分

倒着扫一遍，每格常数次比较加法，时间 O(n)（n 是题数）；dp 长 n+1，空间 O(n)，依赖跨度随 brainpower 变，压不成两格。

落点写成 i+brainpower，自己这格没迈过去，样例一会得 7 而不是 5；nxt 不夹 min(n,…) 会读到表外，brainpower 最大 10⁵、一跳就穿；总分可达 10⁵ 题各 10⁵ 分共 10¹⁰，C++ 用 long long、Java 用 long，Python 整数不设限。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

记住这条「跳过取 dp[i+1]、解决取 points + dp[跳过后的位置],两者取大」,下面每一帧都在套它。倒着填,是因为 dp[i] 依赖更靠后的格子。

先放一个哨兵 dp[7] = 0,表示「越过最后一题之后什么都拿不到」。它是整张表的地基,下面从最右边的第 6 题开始,一格一格往左填。

看第 6 题(紫色,分数 7、做完要跳 1 题)。两条路:跳过它,得右边一格 dp[7] = 0;解决它,拿 7 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 7。蓝色是已经填好的格子。

解决更划算(7 > 0),dp[6] = 7,这一格记下「在这里选择做第 6 题」(绿色)。做完它后面已无可做的题,转移夹到终点哨兵 dp[7]。

第 6 题已落在末尾附近,做完它之后已无题可跳;按规则任何越界位置都统一夹到哨兵 dp[7] = 0,所以转移落到 dp[7]。

看第 5 题(紫色,分数 5、做完要跳 1 题)。两条路:跳过它,得右边一格 dp[6] = 7;解决它,拿 5 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 5。蓝色是已经填好的格子。

跳过更划算(跳过 7 > 解决 5),dp[5] = 7,与右边一格相同,等于「这题不做、留着后面的分」。

选了跳过这格,dp[5] 直接等于右邻 dp[6] = 7,跨度为 1,把决策权留给更靠后的题。

看第 4 题(紫色,分数 6、做完要跳 1 题)。两条路:跳过它,得右边一格 dp[5] = 7;解决它,拿 6 分再跳到第 6 题接上 dp[6] = 7,共 13。蓝色是已经填好的格子。

解决更划算(13 > 7),dp[4] = 13,这一格记下「在这里选择做第 4 题」(绿色)。注意做完它会直接跳到第 6 题。

把「做第 4 题」的代价标出来:红色是它做完被迫跳过的第 5 题,正因为跳过它们,转移才直接落到第 6 题。这就是 brainpower 把「选了就限制后续」量化进 DP 的地方。

看第 3 题(紫色,分数 2、做完要跳 5 题)。两条路:跳过它,得右边一格 dp[4] = 13;解决它,拿 2 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 2。蓝色是已经填好的格子。

跳过更划算(跳过 13 > 解决 2),dp[3] = 13,与右边一格相同,等于「这题不做、留着后面的分」。

选了跳过这格,dp[3] 直接等于右邻 dp[4] = 13,跨度为 1,把决策权留给更靠后的题。

看第 2 题(紫色,分数 4、做完要跳 4 题)。两条路:跳过它,得右边一格 dp[3] = 13;解决它,拿 4 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 4。蓝色是已经填好的格子。

跳过更划算(跳过 13 > 解决 4),dp[2] = 13,与右边一格相同,等于「这题不做、留着后面的分」。

选了跳过这格,dp[2] 直接等于右邻 dp[3] = 13,跨度为 1,把决策权留给更靠后的题。

看第 1 题(紫色,分数 4、做完要跳 3 题)。两条路:跳过它,得右边一格 dp[2] = 13;解决它,拿 4 分再跳到第 5 题接上 dp[5] = 7,共 11。蓝色是已经填好的格子。

跳过更划算(跳过 13 > 解决 11),dp[1] = 13,与右边一格相同,等于「这题不做、留着后面的分」。

选了跳过这格,dp[1] 直接等于右邻 dp[2] = 13,跨度为 1,把决策权留给更靠后的题。

看第 0 题(紫色,分数 3、做完要跳 2 题)。两条路:跳过它,得右边一格 dp[1] = 13;解决它,拿 3 分再跳到第 3 题接上 dp[3] = 13,共 16。蓝色是已经填好的格子。

解决更划算(16 > 13),dp[0] = 16,这一格记下「在这里选择做第 0 题」(绿色)。注意做完它会直接跳到第 3 题。

把「做第 0 题」的代价标出来:红色是它做完被迫跳过的第 1、2 题,正因为跳过它们,转移才直接落到第 3 题。这就是 brainpower 把「选了就限制后续」量化进 DP 的地方。

整张表填满,左边第一格 dp[0] = 16 就是答案。绿色是这条最优路线实际做的题(第 0、4、6 题:分别拿 3、6、7 分,共 16);灰色的题被它们的「跳过」规则越过或不划算而放弃。

边界:单题直接做;brainpower 全为 1 退化成打家劫舍;brainpower 极大则近似只能选一题。

两个延伸:可改写成正序刷表;它是打家劫舍的变跨度推广(brainpower 不固定)。

§3

参考代码

from typing import Listclass Solution:    def mostPoints(self, questions: List[List[int]]) -> int:        n = len(questions)        dp = [0] * (n + 1)        for i in range(n - 1, -1, -1):            points, skip = questions[i]            nxt = min(n, i + skip + 1)            dp[i] = max(dp[i + 1], points + dp[nxt])        return dp[0]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n)，n 是题数。倒着扫一遍,每题做常数次比较与加法
空间：O(n)，dp 数组长 n+1;依赖跨度不定,无法压成常数变量

§5

易错点

✗ 错误写法：从前往后填 dp

✓ 正确写法：从后往前填

dp[i] 要用到更靠后的 dp[i+1] 和 dp[nxt](nxt = min(n, i+brainpower+1)),正着填时右边还没算好;倒着填才能保证依赖项已就绪

✗ 错误写法：跳过位置忘了 min(n, …)

✓ 正确写法：nxt = min(n, i+brainpower+1)

brainpower 很大时 i+brainpower+1 会越过数组末尾,不夹住就会越界;夹到哨兵 dp[n]=0 表示后面无题

✗ 错误写法：用 int 存累加结果

✓ 正确写法：C++/Java 用 long long / long

n 可达 1e5、单题分数大,总分可能超过 32 位 int 上限而溢出

面试追问把动画讲成自己的话

追问能不能改成正序 DP,让 dp[i] 表示「考虑到第 i 题为止的最大分」?

可以,但转移要换成「刷表法」。倒序写的是「站在 i 看后面」(填表/拉取);正序则是「做了 i 题后把贡献推给未来」:做第 i 题时,把 dp_so_far + points 更新到位置 i+brainpower+1 的 dp 上(用 max),同时 dp[i+1] 至少不小于 dp[i](跳过的传递)。两种写法等价,都是 O(n);倒序「拉取」式更直观,面试推荐先讲它。

追问这道题和打家劫舍(LC198)有什么异同?

同:都是「每个位置选或不选、选了会限制后续」的一维线性 DP。异:打家劫舍的限制是固定的「不能选相邻」(跳过恰好 1 个),本题的「跳过数」brainpower 是每题各不相同的变量,所以转移落点 i+brainpower+1 不固定。把打家劫舍看成 brainpower 恒为 1 的特例即可。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 89/108

公平分发饼干

LeetCode 2305 · 中等 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from typing import Listclass Solution: def mostPoints(self, questions: List[List[int]]) -> int: n = len(questions) dp = [0] * (n + 1) for i in range(n - 1, -1, -1): points, skip = questions[i] nxt = min(n, i + skip + 1) dp[i] = max(dp[i + 1], points + dp[nxt]) return dp[0]