I、 121. 买卖股票的最佳时机 (只允许完成一笔交易)

一、题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

二、解题思路 & 代码

2.1 一次遍历

遍历一遍数组，计算每次 到当天为止 的最小股票价格和最大利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minprice = float('inf')
        maxprofit = 0
        for price in prices:
            minprice = min(minprice, price)
            maxprofit = max(maxprofit, price - minprice)
        return maxprofit

复杂度分析

  1. 时间复杂度： O ( n ) O(n) O(n)，遍历了一遍数组。
  2. 空间复杂度： O ( 1 ) O(1) O(1)，使用了有限的变量。

2.2 动态规划

其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。

d p [ i ] dp[i] dp[i] 表示前 i i i 天的最大利润，因为我们始终要使利润最大化，则：

d p [ i ] = m a x ( d p [ i − 1 ] , p r i c e s [ i ] − m i n p r i c e ) dp[i]=max(dp[i−1],prices[i]−minprice) dp[i]=max(dp[i−1],prices[i]−minprice)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0 # 边界条件
        dp = [0] * n
        minprice = prices[0] 

        for i in range(1, n):
            minprice = min(minprice, prices[i])
            dp[i] = max(dp[i - 1], prices[i] - minprice)

        return dp[-1]

参考：

  1. LeetCode题解 & 讨论

======================================================

II、 122. 买卖股票的最佳时机 (尽可能地完成更多的交易)

一、题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

二、解题思路 & 代码

2.1 贪心算法（一次遍历）

“贪心算法” 在每一步总是做出在当前看来最好的选择。

从第 i i i 天（这里 i > = 1 i >= 1 i>=1）开始，与第 i − 1 i - 1 i−1 的股价进行比较，如果股价有上升（严格上升），就将升高的股价 ( p r i c e s [ i ] − p r i c e s [ i − 1 ] ) (prices[i] - prices[i- 1]) (prices[i]−prices[i−1]) 记入总利润，按照这种算法，得到的结果就是符合题意的最大利润。

贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响），因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的。

这道题 “贪心” 的地方在于，对于 “今天的股价 - 昨天的股价”，得到的结果有 3 种可能：（1）正数（2）0（3）负数。

贪心算法的决策是：只加正数。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        N = len(prices)
        for i in range(N-1):
            diff = prices[i + 1] - prices[i]
            if (diff > 0):
                res += diff
        return res

复杂度分析：

  • 时间复杂度：O(N)，这里 N 表示股价数组的长度
  • 空间复杂度：O(1)。

2.2 动态规划

想到动态规划的原因是：可以用贪心算法解决的问题，一般情况下都可以用动态规划

第 1 步：定义状态

状态 d p [ i ] [ j ] dp[i][j] dp[i][j] 定义如下:

  • 第一维 i 表示索引为 i 的那一天（具有前缀性质，即考虑了之前天数的收益）能获得的最大利润；
  • 第二维 j 表示索引为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。

第 2 步：思考状态转移方程

  • 状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；
  • 每一天状态可以转移，也可以不动。状态转移用下图表示：

d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ i ] ) dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])

d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] ) dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i])

说明：

  • 因为不限制交易次数，除了最后一天，每一天的状态可能不变化，也可能转移；
  • 写代码的时候，可以不用对最后一天单独处理，输出最后一天，状态为 0 的时候的值即可。

第 3 步：确定起始
起始的时候：

  • 如果什么都不做， d p [ 0 ] [ 0 ] = 0 dp[0][0] = 0 dp[0][0]=0；
  • 如果买入股票，当前收益是负数，即 d p [ 0 ] [ 1 ] = − p r i c e s [ i ] dp[0][1] = -prices[i] dp[0][1]=−prices[i]；

第 4 步：确定终止
终止的时候，上面也分析了，输出 d p [ l e n − 1 ] [ 0 ] dp[len - 1][0] dp[len−1][0]，因为一定有:
d p [ l e n − 1 ] [ 0 ] > d p [ l e n − 1 ] [ 1 ] dp[len - 1][0] > dp[len - 1][1] dp[len−1][0]>dp[len−1][1]

二维 dp

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        if (N < 2):
            return 0

        # 0：持有现金
        # 1：持有股票
        # 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
        dp = [[0] * 2 for i in range(N)]

        dp[0][0] = 0
        dp[0][1] = -prices[0]

        for i in range(1, N):
            # 这两行调换顺序也是可以的
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

        return dp[N - 1][0]

复杂度分析：

  • 时间复杂度：O(N)，这里 N 表示股价数组的长度。
  • 空间复杂度：O(N)，虽然是二维数组，但是第二维是常数，与问题规模无关。

也可以将状态数组分开设置，使得语义更明确：

二维改进版 dp

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        if (N < 2):
            return 0

        # cash：持有现金
        # hold：持有股票
        # 状态数组
        # 状态转移：cash → hold → cash → hold → cash → hold → cash
        cash = [0] * N
        hold = [0] * N

        cash[0] = 0
        hold[0] = -prices[0]

        for i in range(1, N):
            # 这两行调换顺序也是可以的
            cash[i] = max(cash[i - 1], hold[i - 1] + prices[i])
            hold[i] = max(hold[i - 1], cash[i - 1] - prices[i])

        return cash[N - 1]

一维 dp

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        if (N < 2):
            return 0

        # cash：持有现金
        # hold：持有股票
        # 状态转移：cash → hold → cash → hold → cash → hold → cash

        cash = 0
        hold = -prices[0]

        preCash = cash
        preHold = hold
        for i in range(1, N):
            cash = max(preCash, preHold + prices[i])
            hold = max(preHold, preCash - prices[i])

            preCash = cash
            preHold = hold

        return cash

复杂度分析：

  • 时间复杂度：O(N)，这里 NN 表示股价数组的长度。
  • 空间复杂度：O(1)，分别使用两个滚动变量，将一维数组状态压缩到常数。

参考：

  1. LeetCode题解1

======================================================

III、 123. 买卖股票的最佳时机 (最多可以完成 两笔 交易)

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

二、解题思路 & 代码

状态定义： d p [ i ] [ j ] dp[i][j] dp[i][j] 表示在 [ 0 , i ] [0, i] [0,i] 区间里（这个状态依然是前缀性质的），状态为 j j j 的最大收益。 j j j 的含义如下：

  • j = 0：还未开始交易；
  • j = 1：第 1 次买入一支股票；
  • j = 2：第 1 次卖出一支股票；
  • j = 3：第 2 次买入一支股票；
  • j = 4：第 2 次卖出一支股票。

二维 dp

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        if (N < 2):
            return 0

        # dp[i][j] ，表示 [0, i] 区间里，状态为 j 的最大收益
        # j = 0：什么都不操作
        # j = 1：第 1 次买入一支股票
        # j = 2：第 1 次卖出一支股票
        # j = 3：第 2 次买入一支股票
        # j = 4：第 2 次卖出一支股票

        # 初始化
        dp = [[0] * 5 for i in range(N)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
		
        # 3 状态都还没有发生，因此应该赋值为一个不可能的数
        #因为在更新dp[i][3]的时候可能会出现比0小的数，因为dp[i-1][1]-prices[i]
        #所以这个时候dp[i][3]不能默认是0，相反dp[i][4]就可以默认是0
        for i in range(N):
            dp[i][3] = float("-inf")

        # 状态转移只有 2 种情况：
        # 情况 1：什么都不做
        # 情况 2：由上一个状态转移过来
        for i in range(1, N):
            # j = 0 的值永远是 0
            dp[i][0] = 0
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

        # 最大值只发生在不持股的时候，因此来源有 3 个：j = 0 ,j = 2, j = 4
        return max(0, max(dp[N - 1][2], dp[N - 1][4]))

一维 dp

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        if N < 2:
            return 0

        dp = [0 for _ in range(5)]
        dp[0] = 0
        dp[1] = -prices[0]

        dp[3] = float('-inf')

        # dp[j]：i 表示 [0, i] 区间里，状态为 j 的最大收益
        # j = 0：什么都不操作
        # j = 1：第 1 次买入一支股票
        # j = 2：第 1 次卖出一支股票
        # j = 3：第 2 次买入一支股票
        # j = 4：第 2 次卖出一支股票

        for i in range(1, N):
            dp[0] = 0
            dp[1] = max(dp[1], - prices[i])
            dp[2] = max(dp[2], dp[1] + prices[i])
            dp[3] = max(dp[3], dp[2] - prices[i])
            dp[4] = max(dp[4], dp[3] + prices[i])
        return max(0, dp[2], dp[4])

参考：

  1. LeetCode题解

======================================================

IV、 188. 买卖股票的最佳时机 IV（最多可以完成 k k k 笔交易）

一、题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

二、解题思路 & 代码

d p [ n ] [ k ] [ 2 ] dp[n][k][2] dp[n][k][2] 这里的n表示天数

  • d p [ i ] [ j ] [ 0 ] dp[i][j][0] dp[i][j][0]：表示第 i i i 天交易了 j j j 次时卖出后的累计最大利润
  • d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1]：表示第 i i i 天交易了 j j j 次时买入后的累计最大利润

注意，当 j = = k j==k j==k 时， d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1] 已经没有意义了，因为交易了 k k k 次之后，就不能再买入了。

三维 dp

class Solution(object):
    def maxProfit(self, k, prices):	
        if not prices:
            return 0
        n = len(prices)
        # 当k非常大时转为无限次交易
        if k>n//2:
            dp0,dp1 = 0,-prices[0]
            for i in range(1,n):
                tmp = dp0
                dp0 = max(dp0,dp1+prices[i])
                dp1 = max(dp1,tmp-prices[i])
            return max(dp0,dp1)  
        # 定义三维数组，第i天、交易了多少次、当前的买卖状态 
        dp = [[[0,0] for _ in range(k+1)] for _ in range(n)]
        # 初始化第一天，这里的dp[0][k][1]可以不用管，后面也不会用到
        for i in range(k+1):
            dp[0][i][0] = 0
            dp[0][i][1] = -prices[0]
        for i in range(1,n):
            for j in range(1,k+1):
                # 处理第k次买入
                dp[i][j-1][1] = max(dp[i-1][j-1][1],dp[i-1][j-1][0]-prices[i])
                # 处理第k次卖出
                dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])  
        return dp[-1][k][0]

对三维数组进行压缩，去掉最高维度的天数 n，用二维数组 d p [ k ] [ 2 ] dp[k][2] dp[k][2] 来代替。
这里的 k k k 就是交易了多少次， 2 2 2 表示买卖状态。

由于对 dp 数组进行了压缩，所以内层循环采用的是逆序遍历。
这是因为状态压缩之后，由于少了一个维度，正序遍历会出现状态覆盖的情况，所以改成了逆序遍历。

这种情况在很多dp压缩的时候都会出现，比如背包类型的dp，如果做了状态压缩，也是需要逆序遍历。

二维 dp

class Solution(object):
    def maxProfit(self, k, prices):	
        if not prices:
            return 0
        n = len(prices)
        # 当k非常大时转为无限次交易
        if k>n//2:
            dp0,dp1 = 0,-prices[0]
            for i in range(1,n):
                tmp = dp0
                dp0 = max(dp0,dp1+prices[i])
                dp1 = max(dp1,dp0-prices[i])
            return max(dp0,dp1)
        # 定义二维数组，交易了多少次、当前的买卖状态 
        dp = [[0,0] for _ in range(k+1)]
        for i in range(k+1):
            dp[i][1] = -prices[0]
        for i in range(1,n):
            for j in range(k,0,-1):
                # 处理第k次买入
                dp[j-1][1] = max(dp[j-1][1],dp[j-1][0]-prices[i])
                # 处理第k次卖出
                dp[j][0] = max(dp[j][0],dp[j-1][1]+prices[i])
        return dp[-1][0]

参考：

  1. LeetCode题解