本文目录
定义
贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
常见题型
买卖股票的最佳时机
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res, in_price = 0, float('inf')
for price in prices:
in_price = min(in_price, price)
res = max(res, price-in_price)
return res
买卖股票的最佳时机 II
（可以参与多次交易）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for i in range(len(prices)-1):
res += max(0, prices[i+1]-prices[i])
return res
跳跃游戏
class Solution 大专栏 Leetcode题解-贪心算法 - MaggicQ的博客:
def canJump(self, nums: List[int]) -> bool:
max_ind = 0
for i, n in enumerate(nums):
if i > max_ind: # 超出当前所能到达的最远索引
return False
# max_ind每一步都会更新
# 表示当前所能到达的最远的索引
max_ind = max(max_ind, i+n)
# 成功完成遍历，说明从第一个位置出发能到达最后一个位置
return True
最大子序和
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1]
return max(nums)
判断子序列
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if not s:
return True
pos = t.find(s[0])
if pos == -1:
return False
else:
return self.isSubsequence(s[1:], t[pos+1:])