Medium

题目描述

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的题目，你需要 按顺序 （也就是从问题 0 开始依次解决）对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 分，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定解决还是跳过。

例如，给定 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：

  • 如果问题 0 被解决，你将获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，并解决问题 1 ，你将获得 4 分，但你不能解决问题 2 和 3 。

返回你在考试中能获得的 最大 分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 可以得到最大分数。
- 解决问题 0：获得 3 分，接下来 2 个问题无法解决
- 无法解决问题 1 和 2
- 解决问题 3：获得 2 分
总分：3 + 2 = 5 。没有别的方法获得 5 分或更多分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 可以得到最大分数。
- 跳过问题 0
- 解决问题 1：获得 2 分，接下来 2 个问题无法解决
- 无法解决问题 2 和 3
- 解决问题 4：获得 5 分
总分：2 + 5 = 7 。没有别的方法获得 7 分或更多分。

提示：

  • 1 <= questions.length <= 10^5
  • questions[i].length == 2
  • 1 <= pointsi, brainpoweri <= 10^5

解题思路

这是一个典型的动态规划问题。对于每个问题，我们有两个选择：解决它或跳过它。

思路分析：

我们可以从后往前思考这个问题。设 dp[i] 表示从第 i 个问题开始到考试结束能获得的最大分数。

对于第 i 个问题，我们有两个选择：

  1. 跳过：直接考虑下一个问题，分数为 dp[i+1]
  2. 解决：获得 points[i] 分，但接下来 brainpower[i] 个问题无法解决，下一个能考虑的问题是第 i + brainpower[i] + 1 个，分数为 points[i] + dp[i + brainpower[i] + 1]

状态转移方程：dp[i] = max(dp[i+1], points[i] + dp[i + brainpower[i] + 1])

实现方法：

  1. 自底向上的动态规划：从最后一个问题开始，逐步计算每个位置的最优解
  2. 记忆化递归：使用递归+备忘录的方式实现

两种方法时间复杂度相同，这里给出更直观的自底向上实现。注意边界处理：当索引超出数组范围时，返回 0。

推荐解法：自底向上的动态规划，代码简洁且易于理解。

代码实现

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        vector<long long> dp(n + 1, 0);
        
        for (int i = n - 1; i >= 0; i--) {
            int points = questions[i][0];
            int brainpower = questions[i][1];
            int nextIndex = i + brainpower + 1;
            
            long long skip = dp[i + 1];
            long long solve = points + (nextIndex < n ? dp[nextIndex] : 0);
            
            dp[i] = max(skip, solve);
        }
        
        return dp[0];
    }
};

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, brainpower = questions[i]
            next_index = i + brainpower + 1
            
            skip = dp[i + 1]
            solve = points + (dp[next_index] if next_index < n else 0)
            
            dp[i] = max(skip, solve)
        
        return dp[0]

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--) {
            int points = questions[i][0];
            int brainpower = questions[i][1];
            int nextIndex = i + brainpower + 1;
            
            long skip = dp[i + 1];
            long solve = points + (nextIndex < n ? dp[nextIndex] : 0);
            
            dp[i] = Math.Max(skip, solve);
        }
        
        return dp[0];
    }
}

var mostPoints = function(questions) {
    const n = questions.length;
    const dp = new Array(n + 1).fill(0);
    
    for (let i = n - 1; i >= 0; i--) {
        const [points, brainpower] = questions[i];
        const nextIndex = i + brainpower + 1;
        
        const skip = dp[i + 1];
        const solve = points + (nextIndex < n ? dp[nextIndex] : 0);
        
        dp[i] = Math.max(skip, solve);
    }
    
    return dp[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
动态规划O(n)O(n)
  • 时间复杂度：O(n)，其中 n 是题目数量，我们需要遍历每个问题一次
  • 空间复杂度：O(n)，需要一个长度为 n+1 的 dp 数组存储状态

相关题目