2140. Solving Questions With Brainpower

[Woodyiiiiiii]

这道题涉及到选择的问题，又因为数据量10^5，所以肯定要用动态规划DP的。

如何使用DP解法呢？首先看到可以skip一道题，但要选择下一道题，可以联想到House Robber；但题目中涉及到brain power，选择了答对一道题就会有一定的冷却时间，也就是说会影响到后续的答题，直白点的话在每次题目遍历中要遍历之前的所有题判断冷却时间是否结束，那这样就要有O(n^2)级别的时间复杂度了。

所以关键是，从右往左去遍历数组，从而推出递推方程(看代码)。

class Solution {
    public long mostPoints(int[][] questions) {
        
        int n = questions.length;
        
        long[] dp = new long[n];
        
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1) {
                dp[i] = questions[i][0];
            } else if (i + questions[i][1] + 1 >= n) {
                dp[i] = Math.max(dp[i + 1], questions[i][0]);
            } else {
                dp[i] = Math.max(dp[i + 1], dp[i + questions[i][1] + 1] + questions[i][0]);
            }
        }
        
        return dp[0];
        
    }
}

---

参考资料：

• https://leetcode.com/problems/solving-questions-with-brainpower/
• https://leetcode.cn/problems/solving-questions-with-brainpower/solution/jie-jue-zhi-li-wen-ti-by-leetcode-soluti-ieuq/