题目链接
分析
定义 $dp[i]$ 为解决前 $i$ 道题目可以获得的最大分数，我们发现由于每道题的 $brainpower$ 不固定，我们求解 $dp[i]$ 时要遍历 $j \in [0, i - 1]$ 的所有 $dp[j]$，那么时间复杂度将会是 $O(n^2)$
考虑从后往前遍历，定义 $dp[i]$ 为解决从 $i$ 往后的所有问题可以得到的最大分数
得状态转移方程 $dp[i] = max(dp[i + 1],\ dp[min(n,\ i + brainpower[i] + 1)]$
最终答案为 $dp[0]$
代码实现
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long> dp(n + 1, 0);
for(int i = n - 1; ~i; --i) {
int point = questions[i][0], brainpower = questions[i][1];
dp[i] = max(dp[i + 1], point + dp[min(n, brainpower + i + 1)]);
}
return dp[0];
}
};
复杂度分析
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$
