leetcode-2140

题目

https://leetcode.cn/problems/solving-questions-with-brainpower/description/?envType=daily-question&envId=2025-04-01

分析

• 一个进阶的动态规划题目
• 很有意思的点在于：如果用正常的动态规划思想去解答，会出现，到达一个点，记录这个点的最大值，同时因为这个点的操作影响后续点的操作，非常麻烦。
• 怎么做？ 从后往前
• 根据题意可以知道我们需要的是最大值，可以有
  • dp[i] ：从i出发可以取得的最大值
  • 状态转移方程： dp[i] = max(dp[i+1],questions[i][0]+dp[i+questions[i][1]+1])
  • dp[i+1] ： 从题干可以知道，如果取i，i+1必然不可取，所以dp[i+1]是为i位置跳过时的最大值
  • questions[i][0]: i位置取值
  • dp[i+questions[i][1]+1]： i位置取值时，下一个可以取值的点（也是最大的基数点）
    • 当然，这里需要注意 i + questions[i][1] 不能越界
    • 如果越界了，这一项就没了，只有questions[i][0]
  • 最后答案为 dp[0] ：从0出发

源代码

https://github.com/Norton-Lin/algorithm/blob/master/go/src/leetcode_2140/2025_04_01_2140.go