题目描述
思路解析动画文字版
记住这条「跳过取 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 不固定)。
参考代码
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]复杂度
- 时间：O(n)，n 是题数。倒着扫一遍,每题做常数次比较与加法
- 空间：O(n)，dp 数组长 n+1;依赖跨度不定,无法压成常数变量
易错点
面试追问把动画讲成自己的话
追问能不能改成正序 DP,让 dp[i] 表示「考虑到第 i 题为止的最大分」?
追问这道题和打家劫舍(LC198)有什么异同?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
正则表达式匹配
LeetCode 10 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题