发表于 2025.04.05

• 动态规划题目，我们可以使用一个一维数组dp来记录从当前题目开始到最后一题的最大分数。从后往前遍历，对于每个题目，有两种选择：选择当前题目或者跳过当前题目。我们需要根据题目的分数和脑力消耗来更新dp数组。最终返回dp[0]即可。

  不考虑边界条件的情况下，状态转移方程为：dp[i] = max(dp[i + 1], questions[i][0] + dp[i + questions[i][1] + 1])，其中questions[i][0]表示当前题目的分数，questions[i][1]表示当前题目的脑力消耗（即跳过的题目数量）。

  class Solution {
  public:
      long long mostPoints(vector<vector<int>>& questions) {
          int n = questions.size();
          vector<long long> dp(n, 0);
          for (int i = n - 1; i >= 0; --i) {
              int pt = questions[i][0], brain_power = questions[i][1];
              dp[i] = max(
                  static_cast<long long>(pt) + (i + brain_power + 1 >= n ? 0 : dp[i + brain_power + 1]),
                  (i + 1 >= n ? 0 : dp[i + 1])
              );
          }
          return dp[0];
      }
  };

• LC 题目链接