贪心算法中如何推导贪心策略_如何找出贪心策略

贪心算法的关键：局部最优

在动态规划算法中，我们看到，动态规划算法是为了解决子问题重复而设计的。这些子问题之间并不相互独立，换言之，下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解的。
贪心算法与动态规划算法的不同之处在于，贪心算法对于解决问题的每一个步骤，总选择当前步骤的局部最优（并舍弃了其它可行解），希望以此达到总体最优。
显然，不是所有问题都能使用贪心算法求解，贪心算法也不一定可以找到整体最优解。
贪心算法难点不在于问题求解，而在于对贪心策略正确性的证明。一般来说，贪心算法的正确性证明有替换法、反证法，但是证明并不是本文的重点。本文的重点在于，在实际解题中，有时候直接想出贪心策略需要一定的灵感，但是通过动态规划可以一步步推导出贪心策略。

例子

1. LeetCode 122 买卖股票的最佳时机

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回能获得的最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
1
2
3
4
5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

这个题目，我们可以很容易想到局部最优策略，如果明天价格比今天高，则今天买入明天卖出即可，反之不做操作。这种局部最优策略累积起来，构成了全局最优解。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        cnt = 0
        for i in range(len(prices)-1):
            if prices[i+1] > prices[i]:
                cnt += prices[i+1] - prices[i]
        
        return cnt
1
2
3
4
5
6
7
8
9
10
11
12

我们来看看动态规划如何做。对于某一天，我们可以买入（如果未持有）、卖出（如果已持有）、同一天买入和卖出，所以在某一天，我们的状态是有或者无两种情况（这比按操作讨论更方便一些）。以$f(i,0)$记某一天没有持股的当前收益，以$f(i,1)$记有持股的当前收益。
f ( i , 0 ) = max ⁡ { f ( i − 1 , 0 ) , f ( i − 1 , 1 ) + p r i c e s [ i ] } f ( i , 1 ) = max ⁡ { f ( i − 1 , 1 ) , f ( i − 1 , 0 ) − p r i c e s [ i ] } f(i,0)=\max\{f(i-1,0), f(i-1,1) + prices[i]\}\\ f(i,1)=\max\{f(i-1,1), f(i-1,0) - prices[i]\} f(i,0)=max{f(i−1,0),f(i−1,1)+prices[i]}f(i,1)=max{f(i−1,1),f(i−1,0)−prices[i]}
注意到，$f(i,0)-prices[i]=f(i,1)$，因此
f ( i , 0 ) = max ⁡ { f ( i − 1 , 0 ) , f ( i − 1 , 1 ) + p r i c e s [ i ] } = max ⁡ { f ( i − 1 , 0 ) , f ( i − 1 , 0 ) − p r i c e s [ i − 1 ] + p r i c e s [ i ] } = f ( i − 1 , 0 ) + max ⁡ { 0 , p r i c e s [ i ] − p r i c e s [ i − 1 ] } f(i,0)=\max\{f(i-1,0), f(i-1,1) + prices[i]\} = \max\{f(i-1,0), f(i-1,0)-prices[i-1] + prices[i]\} \\ = f(i-1,0) + \max\{0, prices[i] - prices[i-1]\} f(i,0)=max{f(i−1,0),f(i−1,1)+prices[i]}=max{f(i−1,0),f(i−1,0)−prices[i−1]+prices[i]}=f(i−1,0)+max{0,prices[i]−prices[i−1]}
则得到了贪心策略。

2. LeetCode 714 买卖股票的最佳时机（含手续费）

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
1
2
3
4
5
6
7
8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
1
2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

交易手续费可以在买入或者卖出时候支付，如果计入买入的时候，动态规划的递推式为：
f ( i , 0 ) = max ⁡ { f ( i − 1 , 0 ) , f ( i − 1 , 1 ) + p r i c e s [ i ] } f ( i , 1 ) = max ⁡ { f ( i − 1 , 1 ) , f ( i − 1 , 0 ) − p r i c e s [ i ] − f e e } f(i,0)=\max\{f(i-1,0), f(i-1,1) + prices[i]\}\\ f(i,1)=\max\{f(i-1,1), f(i-1,0) - prices[i]- fee\} f(i,0)=max{f(i−1,0),f(i−1,1)+prices[i]}f(i,1)=max{f(i−1,1),f(i−1,0)−prices[i]−fee}
可以看到，$f(i,1)\le f(i,0)-prices[i]$，因此最终的最优解还是从$f(n,0)$得到。

1. 如果$f(i-1,1)\le f(i-1,0)-prices[i]-fee$
   则$f(i,0)=f(i-1,0),f(i,1)=f(i-1,0)-prices[i]-fee$；此时持股成本为$prices[i]+fee$；
2. 如果$f(i-1,0)-prices[i]-fee\le f(i-1,1)\le f(i-1,0)-prices[i]$
   则$f(i,0)=f(i-1,0),f(i,1)=f(i-1,1)$；此时维持不买入也不卖出；
3. 如果$f(i-1,0)-prices[i]\le f(i-1,1)$
   则$f(i,1)=f(i-1,1),f(i,0)=f(i-1,1)+prices[i]=f(i,1)+prices[i]$；此时卖出套利。

则得到贪心策略，使用一个变量记住成本$prices[i]+fee$，其如果变小的时候，刷新成本，如果可以套利则卖出。但是还有一个点，套利时候可能不在最高点，因此上述情况2中，不买入也不卖出可以视为一种价格置换，如果第$i$天卖出，之后发现后续第$j$天的价格更高，将$prices[j]-prices[i]$也计入收益之后。换言之，此时的虚拟持股成本为$prices[i]$。
上述贪心策略的核心思想是当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        n = len(prices)
        buy = prices[0] + fee
        profit = 0
        for i in range(1, n):
            if prices[i] + fee < buy:
                buy = prices[i] + fee
            elif prices[i] > buy:
                profit += prices[i] - buy
                buy = prices[i]
        return profit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17