JZX轻语：简
LeetCode 2140 - 解决智力问题
发表于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];
}
};