题目链接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[i1],g[i1]);当前选前一个合法位置可选可不选要最大值f[i]Math.max(f[j1],g[j1])nums[i][0];其中如果j1越界时Math.max(f[j1],g[j1])为0③初始化f[n-1]nums[n-1][0]g[n-1]0④填表顺序从右往左⑤返回值max(f[0],g[0])答疑Q1为什么3186. 施咒的最大总伤害不能倒着遍历然后用 j x2快速找到最后一个不合法的位置呢因为上题的x是伤害值是数值上的关系而非索引位置此题我们找的时候不管数值上是什么关系纯是找第j i nums[i]个位置因此上题不能直接这么找空间优化4ms击败100.00%时间复杂度O(N)①状态表示dp[i]:处理到第i题能获得的最高分数②状态转移方程优化思路与F.动态规划-入门DP-打家劫舍3186. 施咒的最大总伤害完全相同综合两个式子当前不选前一个可选可不选要最大值g[i]Math.max(f[i1],g[i1]);→dp[i]dp[i1]当前选前一个合法位置可选可不选要最大值f[i]Math.max(f[j1],g[j1])nums[i][0];→dp[i]dp[j1]nums[i][0]因此dp[i]max(dp[i1],dp[j1]nums[i][0])其中如果j1越界时dp[j1[为0③初始化dp[n-1]要想最大化就必须选因此dp[n-1]nums[n-1][0]④填表顺序从右往左⑤返回值dp[0]Java代码class Solution { public long mostPoints(int[][] nums) { int nnums.length; //选第i题能获得的最高分数 long[] fnew long[n]; f[n-1]nums[n-1][0]; //不选第i题能获得的最高分数 long[] gnew long[n]; g[n-1]0; for(int in-2;i0;i--){ //不选 g[i]Math.max(f[i1],g[i1]); //选 //后nums[i][1]题不能选 int jinums[i][1]; f[i](j1n?Math.max(f[j1],g[j1]):0)nums[i][0]; } return Math.max(f[0],g[0]); } }class Solution { //空间优化版 public long mostPoints(int[][] nums) { int nnums.length; //处理到第i题能获得的最高分数 long[] dpnew long[n]; dp[n-1]nums[n-1][0]; for(int in-2;i0;i--){ //前一个的最大贡献 int jinums[i][1]; long maxCj1n?dp[j1]:0; dp[i]Math.max(dp[i1],maxCnums[i][0]); } return dp[0]; } }