解决智力问题
难度:
标签:
题目描述
代码结果
运行时间: 132 ms, 内存: 57.3 MB
/*
题目思路:
使用Java Stream和并行流来实现动态规划。
对每个题目,我们可以选择做或不做。
在做当前题目时,获得相应分数,并跳过接下来的几个题目。
dp[i] 表示从第 i 题开始能获得的最高分数。
状态转移方程:
1. 如果不做第 i 题:dp[i] = dp[i + 1]
2. 如果做第 i 题:dp[i] = points[i] + dp[i + brainpower[i] + 1]
dp[i] = max(dp[i + 1], points[i] + dp[i + brainpower[i] + 1])
*/
import java.util.stream.IntStream;
public class Solution {
public long mostPoints(int[][] questions) {
int n = questions.length;
long[] dp = new long[n + 1];
IntStream.range(0, n).parallel().forEach(i -> {
int points = questions[i][0];
int brainpower = questions[i][1];
dp[i] = Math.max(dp[i + 1], points + (i + brainpower + 1 < n ? dp[i + brainpower + 1] : 0));
});
return dp[0];
}
}
解释
方法:
这个题解采用了动态规划的方法。从后往前遍历问题数组,对于每个问题,计算解决当前问题和跳过当前问题这两种选择的最大分数。具体来说,如果解决问题i,那么接下来的brainpoweri个问题都不能解决,因此这种选择的总分数是当前问题的分数加上跳过这些问题之后的最大分数;如果跳过问题i,那么总分数就是解决问题i+1的最大分数。最后,比较这两种选择的分数,取较大者作为解决问题i的最大分数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在动态规划中选择从后往前而不是从前往后遍历问题数组?
▷🦆
在计算`dp[i] = max(dp[i + 1], point + (dp[j] if j < n else 0))`时,如何确定`j`的值,即如何计算跳过`brainpoweri`个问题后的位置?
▷🦆
动态规划数组`dp`初始化时,为什么需要长度为`n + 1`,多出的一个元素具体起什么作用?
▷🦆
在处理边界情况时,如果`j`大于等于数组长度`n`,为什么直接使用`0`作为`dp[j]`的值?这样做有什么特殊的考虑吗?
▷