python-leetcode-解决智力问题

2140. 解决智力问题 - 力扣（LeetCode）

这道题是一个典型的 动态规划（Dynamic Programming, DP） 问题，可以使用 自底向上 的方式解决。

思路

1. 定义状态：
   设 dp[i] 表示从第 i 题开始，能获得的最高分数。

2. 状态转移方程：

   • 选择解决第 i 题：
     • 这样可以获得 questions[i][0] 分，并且需要跳过 questions[i][1] 题。
     • 下一次可以从 i + questions[i][1] + 1 题开始，即 dp[i] = questions[i][0] + dp[i + questions[i][1] + 1]。
   • 选择跳过第 i 题：
     • 这样可以从 i+1 题开始，即 dp[i] = dp[i+1]。
   • 取两者的最大值： dp[i]=max⁡(questions[i][0]+dp[i+questions[i][1]+1],dp[i+1])

3. 边界条件：

   • dp[n] = 0 （当超过最后一题时，得分为 0）。

4. 计算顺序：

   • 我们需要从 后往前 计算 dp[i]，因为 dp[i] 依赖于 dp[i+1] 和 dp[i + questions[i][1] + 1]。

代码实现

from typing import List

def mostPoints(questions: List[List[int]]) -> int:
    n = len(questions)
    dp = [0] * (n + 1)  # dp[i] 表示从第 i 题开始能获得的最高分

    for i in range(n - 1, -1, -1):  # 逆序遍历
        points, brainpower = questions[i]
        next_index = i + brainpower + 1  # 下一道可以解的题目
        dp[i] = max(points + (dp[next_index] if next_index < n else 0), dp[i + 1])

    return dp[0]

复杂度分析

• 时间复杂度：O(n)，我们只需遍历 questions 一次，每次 O(1) 计算 dp[i]。
• 空间复杂度：O(n)，用于存储 dp 数组。

示例

输入

questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
print(mostPoints(questions))

输出

5

优化（O(1) 空间）

我们可以只用一个变量来存储 dp[i+1]，这样 dp 数组就不需要额外存储所有状态：

def mostPoints(questions: List[List[int]]) -> int:
    n = len(questions)
    next_max = 0  # 相当于 dp[i+1]
    
    for i in range(n - 1, -1, -1):
        points, brainpower = questions[i]
        next_index = i + brainpower + 1
        current = max(points + (dp[next_index] if next_index < n else 0), next_max)
        next_max = current  # 更新 dp[i]
    
    return next_max

这样，我们将 空间复杂度优化为 O(1)。