F.动态规划-入门DP-打家劫舍：2140. 解决智力问题

题目链接：2140. 解决智力问题（中等）

算法原理：

对比上一题：F.动态规划-入门DP-打家劫舍：3186. 施咒的最大总伤害

体现更简单：避免了准备打家劫舍的值域预处理

体现更困难：从隔2个变成了隔x个，x是未知的，且这个x是后续的，而不是隔前边的

解法：动态规划

7ms击败31.58%

时间复杂度O(N)

①状态表示：

f[i]:选第i题能获得的最高分数

g[i]:不选第i题能获得的最高分数

②状态转移方程：

由于从左往右填表时，我们获取到了当前状态 i ，但此时我们累加时需要的是前 x 题不能选，但这个x却早已经遍历过了，当前状态下的”后续x题不能选“根本没用上，纯🤡了，因此我们需要从后往前遍历，用 j = i +nums[i]找到最后一个不合法的位置，那么 j +1就是第一个合法的状态了，边界状态判断和图解见👇只是遍历顺序改了一下，大致思路是一样的

F.动态规划-入门DP-打家劫舍：3186. 施咒的最大总伤害

当前不选：前一个可选可不选，要最大值

g[i]=Math.max(f[i+1],g[i+1]);

当前选：前一个合法位置可选可不选，要最大值

f[i]=Math.max(f[j+1],g[j+1])+nums[i][0];

其中如果j+1越界时，Math.max(f[j+1],g[j+1])为0

③初始化：

f[n-1]=nums[n-1][0]

g[n-1]=0

④填表顺序：

从右往左

⑤返回值：

max(f[0],g[0])

答疑

Q1：为什么3186. 施咒的最大总伤害不能倒着遍历，然后用 j =x+2快速找到最后一个不合法的位置呢？

因为上题的x是伤害值，是数值上的关系，而非索引位置，此题我们找的时候不管数值上是什么关系，纯是找第j = i +nums[i]个位置，因此上题不能直接这么找

空间优化

4ms击败100.00%

时间复杂度O(N)

①状态表示：

dp[i]:处理到第i题能获得的最高分数

②状态转移方程：

优化思路与F.动态规划-入门DP-打家劫舍：3186. 施咒的最大总伤害完全相同

综合两个式子：

当前不选：前一个可选可不选，要最大值

g[i]=Math.max(f[i+1],g[i+1]);→dp[i]=dp[i+1]

当前选：前一个合法位置可选可不选，要最大值

f[i]=Math.max(f[j+1],g[j+1])+nums[i][0];→dp[i]=dp[j+1]+nums[i][0]

因此dp[i]=max(dp[i+1],dp[j+1]+nums[i][0])

其中如果j+1越界时，dp[j+1[为0

③初始化：

dp[n-1]要想最大化，就必须选，因此dp[n-1]=nums[n-1][0]

④填表顺序：

从右往左

⑤返回值：

dp[0]

Java代码：

class Solution { public long mostPoints(int[][] nums) { int n=nums.length; //选第i题能获得的最高分数 long[] f=new long[n]; f[n-1]=nums[n-1][0]; //不选第i题能获得的最高分数 long[] g=new long[n]; g[n-1]=0; for(int i=n-2;i>=0;i--){ //不选 g[i]=Math.max(f[i+1],g[i+1]); //选 //后nums[i][1]题不能选 int j=i+nums[i][1]; f[i]=(j+1<n?Math.max(f[j+1],g[j+1]):0)+nums[i][0]; } return Math.max(f[0],g[0]); } }

class Solution { //空间优化版 public long mostPoints(int[][] nums) { int n=nums.length; //处理到第i题能获得的最高分数 long[] dp=new long[n]; dp[n-1]=nums[n-1][0]; for(int i=n-2;i>=0;i--){ //前一个的最大贡献 int j=i+nums[i][1]; long maxC=j+1<n?dp[j+1]:0; dp[i]=Math.max(dp[i+1],maxC+nums[i][0]); } return dp[0]; } }