class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
}
};
2140. 解决智力问题
给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。请你返回这场考试里你能获得的 最高 分数。
示例 1：
输入：questions = [[3,2],[4,3],[4,4],[2,5]] 输出：5 解释：解决问题 0 和 3 得到最高分。 - 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。 - 不能解决问题 1 和 2 - 解决问题 3 ：获得 2 分 总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
示例 2：
输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]] 输出：7 解释：解决问题 1 和 4 得到最高分。 - 跳过问题 0 - 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。 - 不能解决问题 2 和 3 - 解决问题 4 ：获得 5 分 总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。
提示：
1 <= questions.length <= 105questions[i].length == 21 <= pointsi, brainpoweri <= 105原站题解
cpp 解法, 执行用时: 404 ms, 内存消耗: 110.2 MB, 提交时间: 2023-09-07 10:57:01
class Solution {
public:
// 正序dp
long long mostPoints(vector<vector<int>> &questions) {
int n = questions.size();
long f[n + 1]; memset(f, 0, sizeof(f));
for (int i = 0; i < n; ++i) {
f[i + 1] = max(f[i + 1], f[i]);
auto &q = questions[i];
int j = min(i + q[1] + 1, n);
f[j] = max(f[j], f[i] + q[0]);
}
return f[n];
}
// 倒序dp
long long mostPoints_2(vector<vector<int>> &questions) {
int n = questions.size();
long f[n + 1];
f[n] = 0L;
for (int i = n - 1; i >= 0; --i) {
auto &q = questions[i];
int j = i + q[1] + 1;
f[i] = max(f[i + 1], q[0] + (j < n ? f[j] : 0));
}
return f[0];
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 96.7 MB, 提交时间: 2023-09-07 10:56:04
class Solution {
// 倒序dp
public long mostPoints(int[][] questions) {
var n = questions.length;
var f = new long[n + 1];
for (var i = n - 1; i >= 0; --i) {
var q = questions[i];
var j = i + q[1] + 1;
f[i] = Math.max(f[i + 1], q[0] + (j < n ? f[j] : 0));
}
return f[0];
}
// 正序dp
public long mostPoints_2(int[][] questions) {
var n = questions.length;
var f = new long[n + 1];
for (var i = 0; i < n; ++i) {
f[i + 1] = Math.max(f[i + 1], f[i]);
var q = questions[i];
var j = Math.min(i + q[1] + 1, n);
f[j] = Math.max(f[j], f[i] + q[0]);
}
return f[n];
}
}
golang 解法, 执行用时: 248 ms, 内存消耗: 19.1 MB, 提交时间: 2023-09-07 10:55:07
// 倒序dp
func mostPoints(questions [][]int) int64 {
n := len(questions)
f := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
q := questions[i]
if j := i + q[1] + 1; j < n {
f[i] = max(f[i+1], q[0]+f[j])
} else {
f[i] = max(f[i+1], q[0])
}
}
return int64(f[0])
}
// 正序dp
func mostPoints_2(questions [][]int) int64 {
n := len(questions)
f := make([]int, n+1)
for i, q := range questions {
f[i+1] = max(f[i+1], f[i])
j := i + q[1] + 1
if j > n {
j = n
}
f[j] = max(f[j], f[i]+q[0])
}
return int64(f[n])
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 396 ms, 内存消耗: 54.3 MB, 提交时间: 2023-09-07 10:53:59
'''
正序dp(刷表法)
'''
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
n = len(questions)
f = [0] * (n + 1)
for i, (point, brainpower) in enumerate(questions):
f[i + 1] = max(f[i + 1], f[i])
j = min(i + brainpower + 1, n)
f[j] = max(f[j], f[i] + point)
return f[n]
python3 解法, 执行用时: 264 ms, 内存消耗: 58.3 MB, 提交时间: 2023-09-07 10:52:38
'''
倒序dp(填表法)
填表法适用于大多数 DP：通过当前状态所依赖的状态，来计算当前状态。
设有 n 个问题，定义 f[i] 表示解决区间 [i,n−1] 内的问题可以获得的最高分数。
倒序遍历问题列表，对于第 i 个问题，我们有两种决策：跳过或解决。
若跳过，则有 f[i]=f[i+1]。
若解决，则需要跳过后续 brainpower[i] 个问题。记 j=i+brainpower[i]+1，则有
f[i] = point[i] + f[j], j < n
f[i] = point[i], j >= n
这两种决策取最大值。
最后答案为 f[0]。
'''
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
n = len(questions)
f = [0] * (n + 1)
for i in range(n - 1, -1, -1):
point, brainpower = questions[i]
j = i + brainpower + 1
f[i] = max(f[i + 1], point + (f[j] if j < n else 0))
return f[0]