【Leetcode 每日一题】2140. 解决智力问题

问题背景

给你一个下标从 $0$ 开始的二维整数数组 $questions$，其中 $questions[i]=[point{s}_i,brainpowe{r}_i]$。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 $0$ 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 $i$ 将让你 获得 $point{s}_i$ 的分数，但是你将 无法 解决接下来的 $brainpowe{r}_i$ 个问题（即只能跳过接下来的 $brainpowe{r}_i$ 个问题）。如果你跳过问题 $i$，你可以对下一个问题决定使用哪种操作。
比方说，给你 $questions=[[3,2],[4,3],[4,4],[2,5]]$：

• 如果问题 $0$ 被解决了， 那么你可以获得 $3$ 分，但你不能解决问题 $1$ 和 $2$。
• 如果你跳过问题 $0$，且解决问题 $1$，你将获得 $4$ 分但是不能解决问题 $2$ 和 $3$。
  请你返回这场考试里你能获得的 最高 分数。

数据约束

• $1\le questions.length\le 10^5$
• $questions[i].length=2$
• $1\le point{s}_i,brainpowe{r}_i\le 10^5$

解题过程

打家劫舍 的进阶版，记忆化每个问题是否解决的情况下得到的分数，从中找出最大值即可。

具体实现

递归

class Solution {public long mostPoints(int[][] questions) {int n = questions.length;long[] memo = new long[n];return dfs(0, questions, memo);}private long dfs(int i, int[][] questions, long[] memo) {if (i >= questions.length) {return 0;}if (memo[i] != 0) {return memo[i];}long skipCur = dfs(i + 1, questions, memo);long cur = dfs(i + 1 + questions[i][1], questions, memo) + questions[i][0];return memo[i] = Math.max(skipCur, cur);}
}

递推

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 j = Math.min(i + questions[i][1] + 1, n);dp[i] = Math.max(dp[i + 1], dp[j] + questions[i][0]);}return dp[0];}
}