解决智力问题

标签: 数组 动态规划

难度: 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 分或者多于 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 <= 105
  • questions[i].length == 2
  • 1 <= pointsi, brainpoweri <= 105

Submission

运行时间: 132 ms

内存: 57.3 MB

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):
            point, brainpower = questions[i]
            j = i + brainpower + 1
            dp[i] = max(dp[i + 1], point + (dp[j] if j < n else 0))
        return dp[0]

Explain

这个题解采用了动态规划的方法。从后往前遍历问题数组，对于每个问题，计算解决当前问题和跳过当前问题这两种选择的最大分数。具体来说，如果解决问题i，那么接下来的brainpoweri个问题都不能解决，因此这种选择的总分数是当前问题的分数加上跳过这些问题之后的最大分数；如果跳过问题i，那么总分数就是解决问题i+1的最大分数。最后，比较这两种选择的分数，取较大者作为解决问题i的最大分数。

时间复杂度: O(n)

空间复杂度: O(n)

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):  # 从后往前遍历问题数组
            point, brainpower = questions[i]  # 当前问题的分数和影响力
            j = i + brainpower + 1  # 解决当前问题后，下一个可以解决的问题的索引
            dp[i] = max(dp[i + 1], point + (dp[j] if j < n else 0))  # 比较解决当前问题和跳过当前问题的最大分数
        return dp[0]  # 返回解决第一个问题的最大分数

Explore

在这个问题中，从后往前遍历是为了确保在计算dp[i]时，所依赖的dp[j]（j > i）已经被计算过并存储了正确的值。如果从前向后遍历，我们在计算dp[i]时，可能还未计算出dp[j]的值，这就会导致我们无法获得正确的最大分数。从后向前保证了在计算每个dp[i]时，所有需要的未来值dp[j]都已正确计算完毕，因此可以直接使用。

在题解中，变量`j`的值由`i + brainpower + 1`计算得出。这里的`i`是当前问题的索引，`brainpower`是当前问题解决后需要跳过的问题数量。加1是因为跳过`brainpower`个问题后，下一个可以解决的问题是位于`i + brainpower + 1`的位置。

在动态规划数组`dp`中，多出的一个元素`dp[n]`用于处理边界情况，即当我们考虑到数组的末尾时，`dp[n]`作为一个额外的状态，表示当所有问题都已被考虑（或跳过）后的总分数。在初始化时设置`dp[n] = 0`，表示如果没有更多问题可以解决，则此时的分数为0。这种设置简化了边界条件的处理，使得我们在计算`dp[i]`时，可以统一处理包括边界在内的所有情况。

如果`j`的值大于等于`n`，意味着根据当前问题的`brainpower`和位置`i`计算出的下一个可解决问题的索引超出了问题数组的范围。在这种情况下，使用`0`作为`dp[j]`的值是因为超出数组范围后没有更多的问题可以解决，因此可以认为超出范围的问题贡献的分数是0。这是一种常见的边界处理方法，确保了算法的简洁性和正确性。