2140. 解决智力问题

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.

• For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:

  • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.

  • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return themaximum points you can earn for the exam.

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]

Output: 5

Explanation: The maximum points can be earned by solving questions 0 and 3.

• Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
• Unable to solve questions 1 and 2
• Solve question 3: Earn 2 points

Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]

Output: 7

Explanation: The maximum points can be earned by solving questions 1 and 4.

• Skip question 0
• Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
• Unable to solve questions 2 and 3
• Solve question 4: Earn 5 points

Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

Constraints:

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

题目大意

给你一个下标从 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 分或者多于 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 分或者多于 7 分。

提示：

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

解题思路

1. dp[i] 表示从 i 开始能获得的最大分数。

2. 状态转移方程：

   • 跳过当前题目：dp[i] = dp[i + 1]
   • 选择当前题目：dp[i] = points[i] + dp[i + brainpower[i] + 1]
   • 最终递推公式：

   dp[i] = Math.max(dp[i + 1], points[i] + dp[i + brainpower[i] + 1]);
   

3. 初始化：

   • dp[n] = 0（超出范围时得分为 0）
   • dp[i] 依赖于 dp[i+1]，所以我们从后往前遍历。

复杂度分析

• 时间复杂度：O(n)，只遍历一次 questions。
• 空间复杂度：O(n)，使用了一个一维数组来存储中间状态。

代码

/**
 * @param {number[][]} questions
 * @return {number}
 */
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 [point, brainpower] = questions[i];
		const nextIndex = i + brainpower + 1;
		const solve = point + (nextIndex < n ? dp[nextIndex] : 0);
		dp[i] = Math.max(dp[i + 1], solve);
	}

	return dp[0];
};

相关题目

题号	标题	题解	标签	难度	力扣
198	打家劫舍	[✓]	数组 动态规划	🟠	🀄️ 🔗
403	青蛙过河		数组 动态规划	🔴	🀄️ 🔗