前言
本题其实是 198. 打家劫舍 的变形题：如果选 $\textit{questions}[i]$，那么接下来的 $\textit{brainpower}_i$ 个问题都不能选。打家劫舍那题相当于 $\textit{brainpower}_i=1$。
一、寻找子问题
在示例 1 中，我们要解决的问题（原问题）是：
- 剩余问题的下标为 $[0,3]$，计算从这些问题中可以获得的最大分数。
讨论 $\textit{questions}[0]$ 选或不选：
- 如果不选，子问题为：剩余问题的下标为 $[1,3]$，计算从这些问题中可以获得的最大分数。
- 如果选，接下来的 $2$ 个问题都不能选，子问题为：剩余问题的下标为 $[3,3]$，计算从这些问题中可以获得的最大分数。
由于选或不选都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。
二、状态定义与状态转移方程
根据上面的讨论，定义状态为 $\textit{dfs}(i)$，表示剩余问题的下标为 $[i,n-1]$，计算从这些问题中可以获得的最大分数。其中 $n$ 是 $\textit{questions}$ 的长度。
讨论 $\textit{questions}[i]$ 选或不选：
- 如果不选，子问题为：剩余问题的下标为 $[i+1,n-1]$，计算从这些问题中可以获得的最大分数，即 $\textit{dfs}(i+1)$。
- 如果选，接下来的 $\textit{brainpower}_i$ 个问题都不能选，子问题为：剩余问题的下标为 $[i+\textit{brainpower}_i+1,n-1]$，计算从这些问题中可以获得的最大分数，即 $\textit{dfs}(i+\textit{brainpower}_i+1)$。
这两种情况取最大值，就得到了 $\textit{dfs}(i)$，即
$$
\textit{dfs}(i) = \max(\textit{dfs}(i+1),\textit{dfs}(i+\textit{brainpower}_i+1)+\textit{points}_i)
$$
对比一下，打家劫舍是 $\textit{dfs}(i) = \max(\textit{dfs}(i+1),\textit{dfs}(i+2)+\textit{nums}_i)$
递归边界：如果 $i\ge n$，那么 $\textit{dfs}(i)=0$。此时没有问题需要解决。
递归入口：$\textit{dfs}(0)$，这是原问题，也是答案。
三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
- 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\textit{memo}$ 数组中。
- 如果一个状态不是第一次遇到（$\textit{memo}$ 中保存的结果不等于 $\textit{memo}$ 的初始值），那么可以直接返回 $\textit{memo}$ 中保存的结果。
注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。本题由于 $\textit{points}_i > 0$，所以也可以把初始值设置为 $0$。
Python 用户可以无视上面这段，直接用 @cache 装饰器。
具体请看视频讲解 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。
class Solution:
def mostPoints(self, questions: List[List[int]]) -> int:
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int) -> int:
if i >= len(questions):
return 0
return max(dfs(i + 1), dfs(i + questions[i][1] + 1) + questions[i][0])
return dfs(0)
class Solution {
public long mostPoints(int[][] questions) {
long[] memo = new long[questions.length];
return dfs(0, questions, memo);
}
private long dfs(int i, int[][] questions, long[] memo) {
if (i >= memo.length) {
return 0;
}
if (memo[i] > 0) { // 之前计算过
return memo[i];
}
long notChoose = dfs(i + 1, questions, memo);
long choose = dfs(i + questions[i][1] + 1, questions, memo) + questions[i][0];
return memo[i] = Math.max(notChoose, choose); // 记忆化
}
}
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long> memo(n);
auto dfs = [&](this auto&& dfs, int i) -> long long {
if (i >= n) {
return 0;
}
long long& res = memo[i]; // 注意这里是引用
if (res) { // 之前计算过
return res;
}
return res = max(dfs(i + 1), dfs(i + questions[i][1] + 1) + questions[i][0]);
};
return dfs(0);
}
};
func mostPoints(questions [][]int) int64 {
n := len(questions)
memo := make([]int64, n)
var dfs func(int) int64
dfs = func(i int) int64 {
if i >= n {
return 0
}
p := &memo[i]
if *p == 0 {
q := questions[i]
*p = max(dfs(i+1), dfs(i+q[1]+1)+int64(q[0]))
}
return *p
}
return dfs(0)
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{questions}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(n)$。
- 空间复杂度：$\mathcal{O}(n)$。保存多少状态，就需要多少空间。
四、1:1 翻译成递推
我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。
具体来说，$f[i]$ 的定义和 $\textit{dfs}(i)$ 的定义是完全一样的，都表示剩余问题的下标为 $[i,n-1]$，计算从这些问题中可以获得的最大分数。
相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：
$$
f[i] = \max(f[i+1], f[j] + \textit{points}_i)
$$
其中 $j = \min(i+\textit{brainpower}_i+1, n)$，这里把 $i>n$ 的状态都视作 $i=n$。
初始值：$f[n] = 0$，翻译自递归边界 $\textit{dfs}(i\ge n)=0$。
答案为 $f[0]$，翻译自递归入口 $\textit{dfs}(0)$。
答疑
问：如何思考循环顺序？什么时候要正序枚举，什么时候要倒序枚举？
答：这里有一个通用的做法：盯着状态转移方程，想一想，要计算 $f[i]$，必须先把 $f[i+1]$ 和 $f[i+\textit{brainpower}_i+1]$ 算出来，那么只有 $i$ 从大到小枚举才能做到。
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):
j = min(i + questions[i][1] + 1, n)
f[i] = max(f[i + 1], f[j] + questions[i][0])
return f[0]
class Solution {
public long mostPoints(int[][] questions) {
int n = questions.length;
long[] f = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
int j = Math.min(i + questions[i][1] + 1, n);
f[i] = Math.max(f[i + 1], f[j] + questions[i][0]);
}
return f[0];
}
}
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long> f(n + 1);
for (int i = n - 1; i >= 0; i--) {
int j = min(i + questions[i][1] + 1, n);
f[i] = max(f[i + 1], f[j] + questions[i][0]);
}
return f[0];
}
};
func mostPoints(questions [][]int) int64 {
n := len(questions)
f := make([]int64, n+1)
for i, q := range slices.Backward(questions) {
j := min(i+q[1]+1, n)
f[i] = max(f[i+1], f[j]+int64(q[0]))
}
return f[0]
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{questions}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
五、另一种做法：从左往右递推
分析
从左往右递推的困难之处在于，并不好确定该从哪里转移过来：已知当前可以解决的问题是 $i$，那么上一个可以解决的问题是什么？
回顾记忆化搜索的过程：
- 如果可以解决问题 $i$，但不去解决它，那么下一个可以解决的问题是 $i+1$，即 $i\to i+1$。
- 如果可以解决问题 $i$，并且去解决它，那么下一个可以解决的问题是 $i+\textit{brainpower}_i+1$，即 $i\to i+\textit{brainpower}_i+1$。
换句话说，已知当前可以解决的问题是 $i$，那么下一个可以解决的问题是容易知道的，有两个。
但反过来，已知当前可以解决的问题是 $i$，那么上一个可以解决的问题有哪些？可能有很多，并不好处理（除非建图，预处理所有转移来源）。
思路
对于这种知道该去哪，但不好知道该从哪来的 DP，可以用刷表法：用当前状态，更新未来的（右边的）状态。
与之对比，上面的做法叫查表法：用之前的（右边的）状态，计算当前状态。
定义 $f[i]$ 表示在能解决问题 $i$ 时，解决区间 $[0,i-1]$ 内的问题可以获得的最高分数。
对于问题 $i$：
- 如果不解决（不选），那么问题 $i+1$ 是能解决的，用 $f[i]$ 更新 $f[i+1]$ 的最大值。
- 如果解决（选），设 $j=\min(i+\textit{brainpower}_i+1,n)$，问题 $j$ 是能解决的，用 $f[i]+\textit{point}_i$ 更新 $f[j]$ 的最大值。
初始值 $f[0]=0$。区间 $[0,-1]$ 是空的，没有问题，得分为 $0$。
答案为 $f[n]$。（把 $n$ 当作一个虚拟的问题）
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]
class Solution {
public long mostPoints(int[][] questions) {
int n = questions.length;
long[] f = new long[n + 1];
for (int i = 0; i < n; i++) {
f[i + 1] = Math.max(f[i + 1], f[i]);
int[] q = questions[i];
int j = Math.min(i + q[1] + 1, n);
f[j] = Math.max(f[j], f[i] + q[0]);
}
return f[n];
}
}
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long> f(n + 1);
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];
}
};
func mostPoints(questions [][]int) int64 {
n := len(questions)
f := make([]int64, n+1)
for i, q := range questions {
f[i+1] = max(f[i+1], f[i])
j := min(i+q[1]+1, n)
f[j] = max(f[j], f[i]+int64(q[0]))
}
return f[n]
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{questions}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
更多相似题目，见 动态规划题单 中的「§7.1 一维 DP」。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
- 【本题相关】动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录
