1696. 跳跃游戏 VI
给你一个下标从 0 开始的整数数组
nums 和一个整数 k 。一开始你在下标
0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。你的目标是到达数组最后一个位置（下标为
n - 1 ），你的 得分 为经过的所有数字之和。请你返回你能得到的 最大得分 。
示例 1：
输入：nums = [1,-1,-2,4,-7,3], k = 2 输出：7 解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。
示例 2：
输入：nums = [10,-5,-2,4,0,3], k = 3 输出：17 解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。
示例 3：
输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 输出：0
提示：
1 <= nums.length, k <= 105
104<= nums[i] <= 104
通过次数7,378提交次数18,492
法 1 动态规划
思路
简单的dp
题解
class Solution: def maxResult(self, nums: List[int], k: int) -> int: # dp[i] 表示落脚点为 nums[i] 时的最大得分 dp = [0] * len(nums) dp[0] = nums[0] for i in range(1, len(nums)): temp = dp[i-k:i] if i - k >= 0 else dp[:i] dp[i] = nums[i] + max(temp) return dp[-1]
法 2 动态规划 + 单调队列
思路
用单调队列来求取 dp 数组最近的k 个值中的最大值
题解
class Solution: def maxResult(self, nums: List[int], k: int) -> int: # dp[i] 表示落脚点为 nums[i] 时的最大得分 dp = [0] * len(nums) dp[0] = nums[0] queue = deque() for i in range(0, len(nums)-1): while queue and i - queue[0] >= k: queue.popleft() while queue and dp[i] > dp[queue[-1]]: queue.pop() queue.append(i) dp[i+1] = nums[i+1] + dp[queue[0]] return dp[-1]