hot100 -- 14.贪心算法

1.买卖股票的最佳时机

方法：

def MaxProfit(prices):max_pro, min_num = 0, float('inf')for num in prices:if num < min_num:min_num = nummax_pro = max(max_pro, num - min_num)return max_pro

2.跳跃游戏

问题：

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

方法1：动态规划

# 方法1：动态规划：记录每一个位置能否到达
def MaxProfit(nums):dp = [False] * len(nums)# 考虑首元素为0的情况if len(nums)==1 and nums[0]==0:return Trueelif nums[0]==0:return Falsedp[0] = Truefor i in range(len(nums)):# 如果能到达，开始跳跃if dp[i]:for j in range(1, nums[i]+1):if i+j < len(nums):dp[i+j] = Trueelse:return True# 不能到达，直接返回else:return Falsereturn dp[-1]

方法2：贪心算法：只关心最终能否到达（推荐）

# 方法2：贪心算法：只关心最终能否到达（最远位置）（推荐）
def MaxProfit(nums):max_reach = 0for i in range(len(nums)):if max_reach < i:                           # 当前位置到不了return Falsemax_reach = max(max_reach, i + nums[i])return max_reach >= (len(nums)-1)