股票买卖问题

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

714 买卖股票+手续费

122 买卖股票无手续费

 

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

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

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

在运行效率上比较，虽然都是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]<minimum:
                minimum = prices[i]
            elif prices[i]-minimum>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