代码随想录算法训练营day35 | 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II
122.买卖股票的最佳时机II
完全想不出来贪心的解法，分解为每天的利润，所有正利润之和为最大利润
class Solution:def maxProfit(self, prices: List[int]) -> int:result = 0for i in range(1, len(prices)):result += max(prices[i] - prices[i-1], 0)return result55. 跳跃游戏
class Solution:def canJump(self, nums: List[int]) -> bool:maxIndex = 0for i in range(len(nums)):maxIndex = max(maxIndex, i+nums[i])if maxIndex <= i and i != len(nums) - 1:return Falsereturn True可以不用遍历完成，只要maxIndex能覆盖到终点就行
class Solution:def canJump(self, nums: List[int]) -> bool:maxIndex = 0i = 0while i <= maxIndex:maxIndex = max(maxIndex, i+nums[i])if maxIndex >= len(nums) - 1:return Truei += 1return False45.跳跃游戏II
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
class Solution:def jump(self, nums: List[int]) -> int:if len(nums) <= 1:return 0curDistance = 0nextDistance = 0result = 0for i in range(len(nums)):nextDistance = max(nextDistance, nums[i] + i)if i == curDistance:result += 1curDistance = nextDistanceif nextDistance >= len(nums) - 1:breakreturn result