本文涉及到的leetcode题目如下：

 

两个问题的前提条件都是一次只能持有一只股票。区别是有无手续费。

解决该问题有两种思路：一种用贪心思想，一种用动态规划。

在编写代码容易程度上比较，贪心思想对于无手续费问题解决方法很简单，对于有手续费问题编程需要技巧；动态规划对于有无手续费是一个通用的模板。

在运行效率上比较，虽然都是O(n)的时间复杂度，贪心方法由于不需要每次都计算max，比动态规划运行速度快一些。

 

1. 贪心

贪心方法对于无手续费的买卖问题很简单。捕捉每一次股票上涨的幅度，避开每一个下跌的幅度。

贪心方法对于有手续费的买卖问题比较复杂。难点在于，在捕捉每一次股票涨幅的同时，需要尽可能减少交易次数。对于如何编写代码实现尽可能少交易，有一些小技巧。

122 无手续费 贪心

　　def maxProfit(self, prices):        """        :type prices: List[int]        :rtype: int        """        profits = 0        for i in range(len(prices)-1):            if prices[i+1]>prices[i]:                profits += (prices[i+1]-prices[i])        return profits

714 有手续费 贪心

　　# leetcode 714 greedy solution　　def maxProfit(self, prices, fee):        """        :type prices: List[int]        :type fee: int        :rtype: int        """        minimum = prices[0]        profit = 0        for i in range(1,len(prices)):            if prices[i]
     
      fee:                profit += prices[i]-minimum-fee                minimum = prices[i] - fee # 处理多次买卖手续费问题        return profit
     

　另一种不太直观不易理解但很巧妙的：

def maxProfit(self, prices, fee):        state = profit = 0         last_price = prices[0]         for price in prices[1:]:                              state += price - last_price            if state > fee:                profit += state - fee                state = fee            else:                if state < 0: state = 0            last_price = price        return profit

　　

2. 动态规划

动态规划的方法是一个通用的模板，稍加改动就可同时解决有、无手续费的两种情况。

每一天有两种操作方法：买入和卖出。因此，我们用buy[i], sell[i]表示第i天买入状态的利润和卖出状态的利润。

初始状态：buy[0]=-prices[0], sell[0]=0

递推公式：

第i天买入状态buy的利润分为两种情况，一种第i-1天没有操作，利润为i-1天buy状态的利润；另一种第i-1天卖出股票，第i天买入股票，因此：

buy[i]=max(buy[i-1], sell[i-1]-prices[i])

同理，第i天卖出状态sell的利润分为两种情况，一种第i-1天没有操作，利润为i-1天sell状态的利润；另一种第i-1天买入股票，第i天卖出股票，因此：

sell[i]=max(sell[i-1], buy[i-1]+prices[i])

对于有手续费的情况，

可以在买入状态计算手续费： buy[i]=max(buy[i-1], sell[i-1]-prices[i]-fee)

也可以在卖出状态计算手续费：sell[i]=max(sell[i-1], buy[i-1]+prices[i]-fee)

122 无手续费

def maxProfit(self, prices):        """        :type prices: List[int]        :rtype: int        """        buy,sell=-prices[0],0        for i in range(1,len(prices)):            buy,sell = max(buy,sell-prices[i]),max(sell,buy+prices[i])        return sell

　　

714 有手续费

def maxProfit(self, prices, fee):        """        :type prices: List[int]        :type fee: int        :rtype: int        """        buy,sell=-prices[0],0        for i in range(1,len(prices)):            buy,sell = max(buy,sell-prices[i]),max(sell,buy+prices[i]-fee) # 卖出时计算手续费        return sell