思想总结

  1. 遍历过程中，隐含尝试了所有可能，避免 O(n^2) 的嵌套循环，感觉这类题不太像动态规划，更像是单纯的时间优化

代表题目

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

1. 理解一：

定义 dp[i] 是遍历到位置 i 时，所能跳到的最大位置，那么如果遍历到 i 时，如果 dp[i-1] >= i 则继续遍历并维护 dp[i]，如果 dp[i-1] < i 说明最大位置都无法到达当前位置，直接返回 false

  • dp[i] = Math.max(dp[i-1], i + nums[i]);

  • 由于只和前一状态有关系，所以可做空间优化 k = Math.max(k, i+nums[i]);

    2. 理解二：

    直接从左到右遍历数组，记录遍历到当前位置 i 时所能跳跃的最大步数 k，一旦 k < i 则不能跳跃到最后则返回 false（此时说明最大步数都不足以到达中间的某个位置更别说最后一个位置了），如果能一直遍历跳出循环则返回 true，最精妙的地方看下面的解释：

  • 例如 [3,2,1,0,4]

第 0 个下标 3 此时可以走 1，2，3 这三个下标，那么当从左到右遍历时，就相当于尝试了这几种情况，当遍历到 4 这个元素时，更新 k 为 4，但是当
这就是比较巧妙的地方，此时只需要动态维护从当前位置所能到达的最大位置 k 即可

45. 跳跃游戏 II

给你一个非负整数数组 nums，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。

官方题解都是用的贪心算法。。。就是每次都走最大的距离，但注意不要访问最后一个元素，因为会多一次跳跃

前置知识 最大子序和。
会了最大子序和，这题也就明白了。
对于环形数组，分两种情况。
(1)答案在数组中间，就是最大子序和。例如[1,-2,3,-2]；
(2)答案在数组两边，例如[5,-3,5]最大的子序和就等于数组的总和SUM-最小的子序和。(一种特殊情况是数组全为负数，也就是SUM-最小子序和==0，最大子序和等于数组中最大的那个)。

作者：lvebe
链接：https://leetcode-cn.com/problems/maximum-sum-circular-subarray/solution/jian-dan-yi-dong-de-ti-jie-by-lvebe-oh0o/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。