5982. 解决智力问题

image.png
image.png

倒序DP

可以记dp[i]为从[i, n-1]范围内得到的最高分数，那么反向遍历questions，对于每个i来说，有两种情况：

  • 不解决此问题：dp[i] = dp[i + 1]
  • 解决此问题，需要跳过后面一些问题，记下一个能够做的问题的下标为j，j = i + brainpower_i + 1：
    • 如果j大于n的话，那么后面的问题都不能做，dp[i] = point_i
    • 如果j小于n的话，dp[i] = point[i] + dp[j]
      1. class Solution {
      2. public:
      3. long long mostPoints(vector<vector<int>> &questions) {
      4.    int n = questions.size();
      5.    vector<long long> dp(n + 1);
      6.    for(int i = n - 1; i >= 0; i--) {
      7.        auto &q = questions[i];
      8.        int j = i + q[1] + 1;
      9.        dp[i] = max(dp[i + 1], q[0] + (j < n ? dp[j] : 0));
      10.    }
      11.    return dp[0];
      12. }
      13. };

      正序刷表

      另一种做法是刷表法：用当前状态，去更新当前状态所影响的状态。
      定义 f[i] 表示解决区间 [0,i] 内的问题可以获得的最高分数。
      对于问题 i，若跳过，则可以更新 f[i+1]=max(f[i+1], f[i])。
      若不跳过，记 j=i + brainpower[i] + 1，则可以更新 f[j]=max(f[j], f[i]+point[i])。
      对于 i=n−1 和 j≥n 的情况，为了简化代码逻辑，我们可以将其更新到 f[n] 中。
      最后答案为 f[n]。
      1. class Solution {
      2. public:
      3. long long mostPoints(vector<vector<int>> &questions) {
      4.    int n = questions.size();
      5.    vector<long long> f(n + 1);
      6.    for (int i = 0; i < n; ++i) {
      7.        f[i + 1] = max(f[i + 1], f[i]);
      8.        auto &q = questions[i];
      9.        int j = min(i + q[1] + 1, n);
      10.        f[j] = max(f[j], f[i] + q[0]);
      11.    }
      12.    return f[n];
      13. }
      14. };