关于贪心

贪心解法没有固定的模板。只有一个感觉。

如果能实现每一阶段局部最优，就可以拓展到全局，得到最优解。

贪心算法一般分为如下四步：

1. 将问题分解为若干个子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

53. 最大子序和

122. 买卖股票的最佳时机 II

题目：
可以无限次的买卖股票，获取的最大利润。同一天可以买卖各一次。

思路：

考虑贪心的思路，可以计算相邻两天买卖的利润，然后取所有的正利润即可。

代码：

res = 0
for i in range(1,len(prices)):
    if prices[i]-prices[i-1] > 0:
        res += prices[i]-prices[i-1]
return res
1
2
3
4
5

55. 跳跃游戏

题目：
数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：

贪心思路，每更新一次index，都计算一次最大的覆盖范围，这个cover可能没变化，也可能是index+nums[i]的值。看cover是否能到最后一个数字。

代码：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        index, cover = 0, 0
        while index <= cover:
            cover  = max(cover, index+nums[index])
            if cover >= len(nums)-1:
                print(index,cover)
                return True
            index += 1
        return False
1
2
3
4
5
6
7
8
9
10