714. 买卖股票的最佳时机含手续费[medium]

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

给定一个整数数组 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.

注意:

< prices.length <= 50000.
< prices[i] < 50000.
<= fee < 50000.

通过次数19,385 | 提交次数29,589

Second Try

2020-06-11

参考题解才找到的动态规划版本，重点是选择正确的状态转换方程。

状态转换分析：

每一天的情况要么有股票要么没有股票，不管是在哪一天验证收益情况，当天肯定手上没有股票才算收益最大。
手上没有股票有两种可能，一是在当天就卖出股票，其次是昨天手上就没有股票，选择的肯定是最大收益的版本。
有股票的也有两种可能，当天买入或是昨天就已经持有，选择的也是最大收益的版本。注意手上有股票的时候，当前收益都是负的。购买最便宜的股票，收益在排序中也最大。
由于每一天两种情况都能往回递推，因此只要考虑起点就可以了。起点有股票的收益是-price[0],没股票的则为0.
状态迁移方程：有股票版本：with_stock[i] = max(with_stock[i-1], no_stock[i-1] - price[i])
状态迁移方程: 无股票版本： no_stock[i] = max(no_stock[i-1], with_stock[i-1] + price[i] - fee)
复杂度：一路往前推进，因此时间复杂度为O(n), 空间复杂度是O(n)
改进可能：由于不停在with_stock和no_stock之间轮换，可以取消数组变成单一变量。

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        if len(prices) <=1:
            return 0
        n = len(prices)
        no_stock = ["" for i in range(n)]
        with_stock = no_stock + []
        no_stock[0], with_stock[0] = 0, -prices[0]
        for i in range(1, n):
            with_stock[i] = max(with_stock[i-1], no_stock[i-1] - prices[i])
            no_stock[i] = max(no_stock[i-1], with_stock[i-1] + prices[i] - fee)
        return no_stock[-1]

执行用时 :792 ms, 在所有 Python 提交中击败了61.88%的用户
内存消耗 :18.7 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-06-10

超出时间限制,不通过。

由于我受到了之前硬币找零题目的影响，使用的是从最后一天开始往前遍历的写法，相当于暴力版本了，超时无法通过。

状态转移分析：

考虑在第n天卖出，买入那天则为[1, n-1]区间中。考虑买入为第i天，则当前收益dp(n) = dp(n-i-1) + (price[n] - price[i])。
如果第i天价格比第n天高，则该区间没有合适的操作，dp(n) = dp(n-i)。
综合两个方程，从dp(n)到dp(n-i-1)实现了状态迁移，因此问题可以被解决。
对于买入区间[1, n-1]则参考凑硬币题目，需要遍历所有的可能。
由于对于每一天可能都需要遍历前i天，因此复杂度为O(n^2)指数级别，更何况一开始为了加速把所有可能的交易都保存了起来，也是O(n^2)级别。

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        n = len(prices)
        cache = [[-1 for i in range(n + 1)] for j in range(n + 1)]
        for i in range(1, n):
            for j in range(i+1, n+1):
                if prices[j-1] - prices[i-1] - fee >  0:
                    cache[i][j] = prices[j-1] - prices[i-1] - fee
        # print(cache)
        memo = [-1 for i in range(n+1)]
        def dp(n):
            """ sell at point n """
            # print('wtffff',n)
            if n <= 0:
                return 0
            if memo[n] != -1:
                return memo[n]
            rv = float("-inf")
            for period in range(1, n):
                if cache[n - period][n] == -1:
                    rv = max(rv, dp(n - period))
                else:
                    rv = max(rv, dp(n - period - 1) + cache[n - period][n])
            memo[n] = rv if rv != float("-inf") else 0
            return memo[n]
        dp(n)
        return memo[-1]

bug version

第n天的函数为dp(n)，保存在memo[n-1]。但是在函数计算的遍历递归中，dp(n-1-period)的操作又把第n天当作dp(n-1)来计算，导致了bug。

问题在于多个缓存列表里使用n-1代表n,函数调用里又直接使用n代表n，这种混淆容易出现bug，还是考虑成一致比较安全，就算多一个位置空间。

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        n = len(prices)
        cache = [[-1 for i in range(n)] for j in range(n)]
        for i in range(n-1):
            for j in range(i+1, n):
                if prices[j] - prices[i] - fee >  0:
                    cache[i][j] = prices[j] - prices[i] - fee
        print(cache)
        memo = [-1 for i in range(n)]
        def dp(n):
            """ sell at point n """
            if n <= 0:
                return 0
            if memo[n-1] != -1:
                return memo[n-1]
            rv = float("-inf")
            for period in range(0, n):
                if cache[n - 1 - period][n - 1] == -1:
                    rv = max(rv, dp(n - 1 - period))
                else:
                    if n == 6:
                        print(n-2-period, dp(n-2 - period), cache[n - 1 - period][n - 1])
                    rv = max(rv, dp(n - 1 - (period + 1)) + cache[n - 1 - period][n - 1])
            memo[n-1] = rv if rv != float("-inf") else 0
            return memo[n-1]
        dp(n)
        print(memo)
        return memo[-1]

        

输入

[1,3,2,8,4,9]
2

输出

预期结果

stdout

[[-1, -1, -1, 5, 1, 6], [-1, -1, -1, 3, -1, 4], [-1, -1, -1, 4, -1, 5], [-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, 3], [-1, -1, -1, -1, -1, -1]]
(3, 0, 3)
(1, 0, 5)
(0, 0, 4)
(-1, 0, 6)
[0, 0, 0, 5, 5, 6]

714. 买卖股票的最佳时机含手续费[medium]​

Second Try​

First Try​

714. 买卖股票的最佳时机含手续费[medium]

Second Try

First Try