方法思路

本题可以通过动态规划来解决，其思路类似于背包问题中的选择与不选择当前物品的决策。每个问题可以选择解决或不解决，解决当前问题会获得分数，但必须跳过后续若干个问题。我们需要通过动态规划来记录每个位置的最大分数，从而得到最终结果。

类比背包问题

在背包问题中，每个物品可以选择拿或不拿，拿的话会占用一定容量并获得价值。这里的问题类似，每个问题可以选择解决或不解决，解决的话会获得分数，但必须跳过后续若干个问题，相当于占用了后续的位置。因此，我们可以将每个问题视为一个物品，其价值为对应的分数，而选择该物品会影响后续物品的选择。

解决思路

  1. 状态定义：定义 f[i] 表示处理到第 i 个问题时的最大分数。
  2. 状态转移：
    • 不解决当前问题：此时最大分数直接传递到下一个问题，即 f[i+1] = max(f[i+1], f[i])。
    • 解决当前问题：获得当前问题的分数，并跳过后续若干个问题，更新对应位置的最大分数。具体来说，解决第 i 个问题后，下一个可处理的问题位置为 j = i + brainpower + 1，这里需要确保 j 不超过总问题数 n。然后更新 f[j] = max(f[j], f[i] + score)。
  3. 初始化：f[0] 初始化为 0，表示初始状态没有处理任何问题时的分数为 0。
  4. 结果：最终结果为 f[n]，即处理完所有问题后的最大分数。

复杂度

  1. 时间复杂度：O(n)
  2. 空间复杂度：O(n)

解决代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1]; // dp[i] 表示处理到第i个问题时的最大分数
        
        for (int i = 0; i < n; i++) {
            // 不解决当前问题，直接传递到下一个问题
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
            
            // 解决当前问题，计算下一个可处理的问题位置
            int j = Math.min(i + questions[i][1] + 1, n);
            dp[j] = Math.max(dp[j], dp[i] + questions[i][0]);
        }
        
        return dp[n];
    }
}

代码解释

  • 初始化：dp 数组长度为 n + 1，初始值均为 0。
  • 遍历每个问题：对于每个问题 i，首先处理不解决的情况，将当前最大分数传递到下一个位置。
  • 处理解决当前问题的情况：计算下一个可处理的问题位置 j，并更新该位置的最大分数。
  • 返回结果：最终结果存储在 dp[n] 中，表示处理完所有问题后的最大分数。
  • 注意：数组dp[n]需要用long才能通过全部样例。