解决智力题 图解题解
这道题到底在问什么
- 输入
- questions=[[3,2],[4,3],[4,4],[2,5]]
- 输出
- 5(做第 0 题和第 3 题)
- 输入
- questions=[[1,1],[2,2],[3,3],[4,4],[5,5]]
- 输出
- 7
最优解：一步一步想明白
- 3记住这条「跳过取 dp[i+1]、解决取 points + dp[跳过后的位置],两者取大」,下面每一帧都在套它。倒着填,是因为 dp[i] 依赖更靠后的格子。
- 4先放一个哨兵 dp[7] = 0,表示「越过最后一题之后什么都拿不到」。它是整张表的地基,下面从最右边的第 6 题开始,一格一格往左填。
- 5看第 6 题(紫色,分数 7、做完要跳 1 题)。两条路:跳过它,得右边一格 dp[7] = 0;解决它,拿 7 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 7。蓝色是已经填好的格子。
- 6解决更划算(7 > 0),dp[6] = 7,这一格记下「在这里选择做第 6 题」(绿色)。做完它后面已无可做的题,转移夹到终点哨兵 dp[7]。
- 7第 6 题已落在末尾附近,做完它之后已无题可跳;按规则任何越界位置都统一夹到哨兵 dp[7] = 0,所以转移落到 dp[7]。
- 8看第 5 题(紫色,分数 5、做完要跳 1 题)。两条路:跳过它,得右边一格 dp[6] = 7;解决它,拿 5 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 5。蓝色是已经填好的格子。
- 9跳过更划算(跳过 7 > 解决 5),dp[5] = 7,与右边一格相同,等于「这题不做、留着后面的分」。
- 10选了跳过这格,dp[5] 直接等于右邻 dp[6] = 7,跨度为 1,把决策权留给更靠后的题。
- 11看第 4 题(紫色,分数 6、做完要跳 1 题)。两条路:跳过它,得右边一格 dp[5] = 7;解决它,拿 6 分再跳到第 6 题接上 dp[6] = 7,共 13。蓝色是已经填好的格子。
- 12解决更划算(13 > 7),dp[4] = 13,这一格记下「在这里选择做第 4 题」(绿色)。注意做完它会直接跳到第 6 题。
- 13把「做第 4 题」的代价标出来:红色是它做完被迫跳过的第 5 题,正因为跳过它们,转移才直接落到第 6 题。这就是 brainpower 把「选了就限制后续」量化进 DP 的地方。
- 14看第 3 题(紫色,分数 2、做完要跳 5 题)。两条路:跳过它,得右边一格 dp[4] = 13;解决它,拿 2 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 2。蓝色是已经填好的格子。
- 15跳过更划算(跳过 13 > 解决 2),dp[3] = 13,与右边一格相同,等于「这题不做、留着后面的分」。
- 16选了跳过这格,dp[3] 直接等于右邻 dp[4] = 13,跨度为 1,把决策权留给更靠后的题。
- 17看第 2 题(紫色,分数 4、做完要跳 4 题)。两条路:跳过它,得右边一格 dp[3] = 13;解决它,拿 4 分再跳到终点哨兵 dp[7]接上 dp[7] = 0,共 4。蓝色是已经填好的格子。
- 18跳过更划算(跳过 13 > 解决 4),dp[2] = 13,与右边一格相同,等于「这题不做、留着后面的分」。
- 19选了跳过这格,dp[2] 直接等于右邻 dp[3] = 13,跨度为 1,把决策权留给更靠后的题。
- 20看第 1 题(紫色,分数 4、做完要跳 3 题)。两条路:跳过它,得右边一格 dp[2] = 13;解决它,拿 4 分再跳到第 5 题接上 dp[5] = 7,共 11。蓝色是已经填好的格子。
- 21跳过更划算(跳过 13 > 解决 11),dp[1] = 13,与右边一格相同,等于「这题不做、留着后面的分」。
- 22选了跳过这格,dp[1] 直接等于右邻 dp[2] = 13,跨度为 1,把决策权留给更靠后的题。
- 23看第 0 题(紫色,分数 3、做完要跳 2 题)。两条路:跳过它,得右边一格 dp[1] = 13;解决它,拿 3 分再跳到第 3 题接上 dp[3] = 13,共 16。蓝色是已经填好的格子。
- 24解决更划算(16 > 13),dp[0] = 16,这一格记下「在这里选择做第 0 题」(绿色)。注意做完它会直接跳到第 3 题。
- 25把「做第 0 题」的代价标出来:红色是它做完被迫跳过的第 1、2 题,正因为跳过它们,转移才直接落到第 3 题。这就是 brainpower 把「选了就限制后续」量化进 DP 的地方。
- 26整张表填满,左边第一格 dp[0] = 16 就是答案。绿色是这条最优路线实际做的题(第 0、4、6 题:分别拿 3、6、7 分,共 16);灰色的题被它们的「跳过」规则越过或不划算而放弃。
⚠️ 容易写错的地方
✗ 错：从前往后填 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 上限而溢出
完整代码（Python / C++ / Java）
Python
from typing import List
class 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]C++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long> dp(n + 1);
for (int i = n - 1; i >= 0; --i) {
int nxt = min(n, i + questions[i][1] + 1);
dp[i] = max(dp[i+1], (long long)questions[i][0] + dp[nxt]);
}
return dp[0];
}
};Java
import java.util.*;
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--) {
int next = Math.min(n, i + questions[i][1] + 1);
dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[next]);
}
return dp[0];
}
}复杂度
时间
O(n)
n 是题数。倒着扫一遍,每题做常数次比较与加法
空间
O(n)
dp 数组长 n+1;依赖跨度不定,无法压成常数变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 解决智力题 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能改成正序 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 的特例即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 解决智力题 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。