本文主要是介绍Day32代码随想录贪心part02：122.买卖股票的最佳时机II（主要是动态规划，少数可以用贪心）、55. 跳跃游戏）、45.跳跃游戏II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Day32 贪心part02
122.买卖股票的最佳时机II（主要是动态规划，少数可以用贪心）
**题意：**给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路：
（1）首先多天的利润其实可以拆分成单天的利润：p[3]-p[0] = (p[3]-p[2])+(p[2]-p[1])+(p[1]-p[0])把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
（2）如果之前的利润是正数才有正向作用：所以只收集每天的正利润（局部最优），全局最优就是总利润最大
class Solution:def maxProfit(self, prices: List[int]) -> int:res = 0for i in range(1, len(prices)): #i从1开始是因为至少要第一天买入pro = prices[i] - prices[i-1]if pro >0:res += proreturn res
55. 跳跃游戏
leetcode链接：55. 跳跃游戏 - 力扣（LeetCode）
题意：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例 1:
- 输入: [2,3,1,1,4]
- 输出: true
- 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
思路：如果一开始纠结每个位置应该跳几步，那么这道题就非常复杂了；但是我们可以考虑覆盖范围！只要在覆盖范围内就一定能跳到，就不要纠结跳几步了
注意边界：如果就1个元素，那么一定是可以覆盖的
class Solution:def canJump(self, nums: List[int]) -> bool:cover = 1if len(nums) == 1:return Truefor i in range(len(nums)-1):if i+1<=cover: # 这一步是很重要的，如果现在走的这一步都没有覆盖到，接着也走不下去了cover = max(cover, i+nums[i]+1) # 在cover和当前步i能cover的里面选择更大的范围if cover >= len(nums):# 发现满足条件直接返回不用后序了return Truereturn False
45.跳跃游戏II（这题比较绕的）
leetcode题目：. - 力扣（LeetCode）
题意：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
- 输入: [2,3,1,1,4]
- 输出: 2
- 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置
思路：用最少的步数增加覆盖范围，一旦覆盖到终点就输出即可
也就是说当前步数可以覆盖到的范围，如果没有到终点那么需要步数+1的；下一步可以走到的最多是在当前步可以覆盖到的区间内的；以这个示例举例，当前步2可以覆盖到[3,1]但是肯定到不了终点，所以步数+1; 下一段是3走的最多，可以到终点
定义：cur_cover当前能遍历到的最大index
next_cover下一步能遍历到的最大index，一定是大于等于cur_cover的
首先在cur_cover的能力范围内，先找到最大的next_cover，然后此时如果i==cur_cover时也就是没到终点，那step+=1代表需要走下一步
模拟：
（1）cur_cover = 0, i=0时是只遍历到2, next_cover最大为2，此时i==cur_cover，step =1
（2）cur_cover = 2, i=1,2时遍历到[3,1], next_cover最大为4,3，此时i==cur_cover，step =2, break
class Solution:def jump(self, nums: List[int]) -> int:cur_cover = 0 # 当前覆盖最远距离下标next_cover = 0 # 下一步覆盖最远距离下标min_step = 0if len(nums)==1:return min_stepfor i in range(len(nums)-1):next_cover = max(next_cover, i+nums[i])if i==cur_cover:min_step += 1if next_cover >= len(nums)-1:breakcur_cover = next_coverreturn min_step
这篇关于Day32代码随想录贪心part02：122.买卖股票的最佳时机II（主要是动态规划，少数可以用贪心）、55. 跳跃游戏）、45.跳跃游戏II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
