解决智力题 图解题解

解决智力题到底在选什么

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 整数不设限。

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];
    }
}