leetcode
leetcode 1901 ~ 1950
解决智力问题

解决智力问题

难度:

标签:

题目描述

代码结果

运行时间: 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]时,所依赖的dp[j](j > i)已经被计算过并存储了正确的值。如果从前向后遍历,我们在计算dp[i]时,可能还未计算出dp[j]的值,这就会导致我们无法获得正确的最大分数。从后向前保证了在计算每个dp[i]时,所有需要的未来值dp[j]都已正确计算完毕,因此可以直接使用。
🦆
在计算`dp[i] = max(dp[i + 1], point + (dp[j] if j < n else 0))`时,如何确定`j`的值,即如何计算跳过`brainpoweri`个问题后的位置?
在题解中,变量`j`的值由`i + brainpower + 1`计算得出。这里的`i`是当前问题的索引,`brainpower`是当前问题解决后需要跳过的问题数量。加1是因为跳过`brainpower`个问题后,下一个可以解决的问题是位于`i + brainpower + 1`的位置。
🦆
动态规划数组`dp`初始化时,为什么需要长度为`n + 1`,多出的一个元素具体起什么作用?
在动态规划数组`dp`中,多出的一个元素`dp[n]`用于处理边界情况,即当我们考虑到数组的末尾时,`dp[n]`作为一个额外的状态,表示当所有问题都已被考虑(或跳过)后的总分数。在初始化时设置`dp[n] = 0`,表示如果没有更多问题可以解决,则此时的分数为0。这种设置简化了边界条件的处理,使得我们在计算`dp[i]`时,可以统一处理包括边界在内的所有情况。
🦆
在处理边界情况时,如果`j`大于等于数组长度`n`,为什么直接使用`0`作为`dp[j]`的值?这样做有什么特殊的考虑吗?
如果`j`的值大于等于`n`,意味着根据当前问题的`brainpower`和位置`i`计算出的下一个可解决问题的索引超出了问题数组的范围。在这种情况下,使用`0`作为`dp[j]`的值是因为超出数组范围后没有更多的问题可以解决,因此可以认为超出范围的问题贡献的分数是0。这是一种常见的边界处理方法,确保了算法的简洁性和正确性。

相关问题