[数据结构与算法][dp(选与不选问题)]5982：解决智力问题(medium)

题目：

题解：

分为正向dp和倒序dp，具体可看思路：

---

代码如下：

class Solution {
public:
    // 倒序dp(查表法)：f[i]表示[i,n-1]之间问题所能得到的最大分数
    /*状态转移方程：f[i]=max(f[i+1],q[0]+(j<n?f[j]:0))；对于问题i，我们可以选择解决，也可以选择跳过;
    选择跳过问题i的话，则f[i]=f[i+1]表示f[i]为[i+1,n-1]所能获得最大分数；选择解决问题i的话，我们就要跳过q[1]个问题了，那么最终落到j=i+q[1]+1号问题上，若j<n，那么我们加上问题获得最大分数f[j]即可；若就j>=n，则跳过了，只能加上0了*/
    using LL = long long;
    long long mostPoints_1(vector<vector<int>>& que) {
        int n=que.size();
        LL f[n+1];
        memset(f,0,sizeof f);
        for(int i=n-1;i>=0;i--){
            auto& q=que[i];
            int j=i+q[1]+1;
            f[i]=max(f[i+1],q[0]+(j<n?f[j]:0));
        }
        return f[0];
    }

    // 正向dp(刷表法)：定义f[i]表示解决区间[0,i]内的问题可以获得的最高分数
    long long mostPoints(vector<vector<int>>& que){
        int n=que.size();
        LL f[n+1];
        memset(f,0,sizeof f);
        for(int i=0;i<n;++i){
            // 跳过问题i；然后用来更新f[i+1]，即不解决问题i+1之前的问题i
            f[i+1]=max(f[i+1],f[i]);
            auto &q=que[i];
            int j=min(n,i+q[1]+1);
            // 解决问题i；则解决问题j的最高分数为f[i]+q[0]与f[j]取max了
            f[j]=max(f[j],f[i]+q[0]);
        }
        return f[n];
    }
};