[数据结构与算法]leetcode刷题集：股票问题六讲【动态规划】（python代码）

参考了 股票问题系列通解（转载翻译）

股票问题六讲

结论

先把结论放在这里：

题目要求不能同时参与多笔交易，即最多只能持有一支股票

121. 买卖股票的最佳时机

leetcode

题目

给定一个数组 $prices$ ，它的第 $i$ 个元素 $prices[i]$ 表示一支给定股票第 $i$ 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

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

提示：

• $1<=prices.length<=10^5$
• $0<=prices[i]<=10^4$

思路

动态规划

• 状态表达式：

  • $dp[i][0]$：第 $i$ 天结束时，持有0份股票的情况下，最大收益
  • $dp[i][1]$：第 $i$ 天结束时，持有1份股票的情况下，最大收益

• 状态转移方程：

  • 第 $i$ 天时，在已经持有1支股票的前提下，不进行任何操作，保持不变；或者在从未买入过股票的前提下，以 $prices[i]$ 价格买入股票
    • d p [ i ] [ 1 ] = m a x { d p [ i ? 1 ] [ 1 ] , ? p r i c e s [ i ] } dp[i][1]=max\{dp[i-1][1], \textcolor{#DC5771}{-prices[i]}\} dp[i][1]=max{dp[i?1][1],?prices[i]}
  • 第 $i$ 天时，在没有持有股票的前提下，不进行任何操作，保持不变；或者在已经持有1支股票的前提下，以 $prices[i]$ 价格卖出股票
    • 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]}

• 初始化边界

  • $dp[0][0]=0$ ：

  • $dp[0][1]=?prices[0]$：第0天买入

  • 说明：因为这里初始化 dp 的大小是n，遍历值是第 0～n-1 天，如果初始化第 -1 天，应该是

    • $dp[?1][0]=0$
    • $dp[?1][1]=?inf$

• 返回值

  • $dp[n?1][0]$ ：卖掉后的最大收益

代码

时间复杂度为$O(n)$，空间复杂度为 $O(n)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0, 0] for _ in range(n)]
        dp[0][1] = -prices[0]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])  
            # 第i天买入
            dp[i][1] = max(dp[i-1][1], -prices[i])  

        return dp[-1][0]

空间优化，时间复杂度为$O(n)$，空间复杂度为 $O(1)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [0, -prices[0]]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            newdp0 = max(dp[0], dp[1]+prices[i]) 
            # 第i天买入
            newdp1 = max(dp[1], -prices[i])
            dp[0], dp[1] = newdp0, newdp1

        return dp[0]

122. 买卖股票的最佳时机 II

leetcode

题目

给你一个整数数组 $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 。

示例 2：

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

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

• $1<=prices.length<=3?10^4$
• $0<=prices[i]<=10^4$

思路

动态规划，基本同 I

• 状态表达式：

  • $dp[i][0]$：第 $i$ 天结束时，持有0份股票的情况下，最大收益
  • $dp[i][1]$：第 $i$ 天结束时，持有1份股票的情况下，最大收益

• 状态转移方程：

  • 第 $i$ 天时，在已经持有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], \textcolor{#DC5771}{dp[i-1][0]-prices[i]}\} dp[i][1]=max{dp[i?1][1],dp[i?1][0]?prices[i]}
  • 第 $i$ 天时，在不持有股票的前提下，不进行任何操作，保持不变；或者在已经持有1支股票的前提下，以 $prices[i]$ 价格卖出股票
    • 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]}

• 初始化边界

  • $dp[0][0]=0$ ：
  • $dp[0][1]=?prices[0]$：第0天买入
  • 说明：因为这里初始化 dp 的大小是n，遍历值是第 0～n-1 天，第 -1 天，应该是
    • $dp[?1][0]=0$
    • $dp[?1][1]=?inf$

• 返回值

  • $dp[n?1][0]$ ：卖掉后的最大收益

代码

时间复杂度为$O(n)$，空间复杂度为 $O(n)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0, 0] for _ in range(n)]
        dp[0][1] = -prices[0]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])  
            # 第i天买入
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])  

        return dp[-1][0]

空间优化，时间复杂度为$O(n)$，空间复杂度为 $O(1)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [0, -prices[0]]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            newdp0 = max(dp[0], dp[1]+prices[i]) 
            # 第i天买入
            newdp1 = max(dp[1], dp[0]-prices[i])
            dp[0], dp[1] = newdp0, newdp1

        return dp[0]

进一步优化掉 newdp0 和 newdp1 这两个变量

如果先更新 $dp[0]$ 再更新 $dp[1]$，相当于当天卖出再买入

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [0, -prices[0]]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp[0] = max(dp[0], dp[1]+prices[i]) 
            # 第i天买入
            dp[1] = max(dp[1], dp[0]-prices[i])

        return dp[0]

123. 买卖股票的最佳时机 III

leetcode

题目

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

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

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

示例 1:

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

示例 2：

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

示例 3：

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

示例 4：

输入：prices = [1]
输出：0

提示：

• $1<=prices.length<=10^5$
• $0<=prices[i]<=10^5$

思路

动态规划，在 I 和 II 的基础上，新增了一个维度

由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：

• 未进行过任何操作；
• 只进行过一次买操作；
• 进行了一次买操作和一次卖操作，即完成了一笔交易；
• 在完成了一笔交易的前提下，进行了第二次买操作；
• 完成了全部两笔交易。

第一个状态的利润显然为 0，因此我们可以不用将其记录。

其它四个状态为：

• 只进行过一次买操作：$dp[i][1][1]$
• 进行了一次买操作和一次卖操作，即完成了一笔交易：$dp[i][1][0]$
• 在完成了一笔交易的前提下，进行了第二次买操作：$dp[i][2][1]$
• 完成了全部两笔交易：$dp[i][2][0]$

定义状态转移数组 dp[天数][买入的次数][当前是否持股]

注意：这里定义的是“买入的次数”

• 状态表达式：

  • $dp[i][0][0]=0$：第 $i$ 天结束时，进行了 $0$ 次交易且在操作后持有0份股票的情况下，最大收益（必然为0）
  • $dp[i][1][1]$：第 $i$ 天结束时，进行了 $1$ 次交易且在操作后持有1份股票的情况下，最大收益
  • $dp[i][1][0]$：第 $i$ 天结束时，进行了 $1$ 次交易且在操作后持有0份股票的情况下，最大收益
  • $dp[i][2][1]$：第 $i$ 天结束时，进行了 $2$ 次交易且在操作后持有1份股票的情况下，最大收益
  • $dp[i][2][0]$：第 $i$ 天结束时，进行了 $2$ 次交易且在操作后持有0份股票的情况下，最大收益

• 状态转移方程：

  • 第 $i$ 天时，在进行过 1 次买操作的前提下不进行任何操作，保持不变；或者在未进行任何操作的前提下以$prices[i]$的价格买入股票
    • d p [ i ] [ 1 ] [ 1 ] = m a x { d p [ i ? 1 ] [ 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] [ 0 ] ? p r i c e s [ i ] } = m a x { d p [ i ? 1 ] [ 1 ] [ 1 ] , ? p r i c e s [ i ] } \begin{aligned}dp[i][1][1]&=max\{dp[i-1][1][1], dp[i-1][0][0]-prices[i]\}\\&=max\{dp[i-1][1][1], -prices[i]\}\end{aligned} dp[i][1][1]?=max{dp[i?1][1][1],dp[i?1][0][0]?prices[i]}=max{dp[i?1][1][1],?prices[i]}?
  • 第 $i$ 天时，在进行过 1 次买操作和 1 次卖操作（完成了 1 笔交易）的前提下不进行任何操作，保持不变；或者在只进行过一次买操作的前提下，以$prices[i]$的价格卖出股票
    • d p [ i ] [ 1 ] [ 0 ] = m a x { d p [ i ? 1 ] [ 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] [ 1 ] + p r i c e s [ i ] } dp[i][1][0]=max\{dp[i-1][1][0], dp[i-1][1][1]+prices[i]\} dp[i][1][0]=max{dp[i?1][1][0],dp[i?1][1][1]+prices[i]}
  • 第 $i$ 天时，在进行过 2 次买操作和 1 次卖操作（完成了 1 笔交易且第二次买）的前提下不进行任何操作，保持不变；或者在只进行过一次买操作和一次卖操作（完成了 1 笔交易）的前提下，以$prices[i]$的价格买入股票
    • d p [ i ] [ 2 ] [ 1 ] = m a x { d p [ i ? 1 ] [ 2 ] [ 1 ] , d p [ i ? 1 ] [ 1 ] [ 0 ] ? p r i c e s [ i ] } dp[i][2][1]=max\{dp[i-1][2][1], dp[i-1][1][0]-prices[i]\} dp[i][2][1]=max{dp[i?1][2][1],dp[i?1][1][0]?prices[i]}
  • 第 $i$ 天时，在进行过 2 次买操作和 2 次卖操作（完成了 2 笔交易）的前提下不进行任何操作，保持不变；或者在进行过 2 次买操作和 1 次卖操作（完成了 1 笔交易且第二次买）的前提下，以$prices[i]$的价格卖出股票
    • d p [ i ] [ 2 ] [ 0 ] = m a x { d p [ i ? 1 ] [ 2 ] [ 0 ] , d p [ i ? 1 ] [ 2 ] [ 1 ] + p r i c e s [ i ] } dp[i][2][0]=max\{dp[i-1][2][0], dp[i-1][2][1]+prices[i]\} dp[i][2][0]=max{dp[i?1][2][0],dp[i?1][2][1]+prices[i]}

即
{ d p [ i ] [ 1 ] [ 1 ] = m a x { d p [ i ? 1 ] [ 1 ] [ 1 ] , ? p r i c e s [ i ] } d p [ i ] [ 1 ] [ 0 ] = m a x { d p [ i ? 1 ] [ 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] [ 1 ] + p r i c e s [ i ] } d p [ i ] [ 2 ] [ 1 ] = m a x { d p [ i ? 1 ] [ 2 ] [ 1 ] , d p [ i ? 1 ] [ 1 ] [ 0 ] ? p r i c e s [ i ] } d p [ i ] [ 2 ] [ 0 ] = m a x { d p [ i ? 1 ] [ 2 ] [ 0 ] , d p [ i ? 1 ] [ 2 ] [ 1 ] + p r i c e s [ i ] } \left\{\begin{array}{l}dp[i][1][1]=max\{dp[i-1][1][1], -prices[i]\} \\dp[i][1][0]=max\{dp[i-1][1][0], dp[i-1][1][1]+prices[i]\} \\ dp[i][2][1]=max\{dp[i-1][2][1], dp[i-1][1][0]-prices[i]\} \\ dp[i][2][0]=max\{dp[i-1][2][0], dp[i-1][2][1]+prices[i]\}\end{array}\right. ? ? ??dp[i][1][1]=max{dp[i?1][1][1],?prices[i]}dp[i][1][0]=max{dp[i?1][1][0],dp[i?1][1][1]+prices[i]}dp[i][2][1]=max{dp[i?1][2][1],dp[i?1][1][0]?prices[i]}dp[i][2][0]=max{dp[i?1][2][0],dp[i?1][2][1]+prices[i]}?

• 初始化边界

  • $dp[0][1][1]=?prices[0]$：第0天买入
  • $dp[0][1][0]=0$：相当于第0天买入、卖出
  • $dp[0][2][1]=?prices[0]$：第0天买入、卖出、再买入
  • $dp[0][2][0]=0$：相当于第0天买入、卖出、再买入、再卖出

• 返回值

  • $dp[n?1][2][0]$ ：完成2笔交易的最大值
  • 分析：由于我们可以进行不超过两笔交易，因此最终的答案在0，$dp[n?1][1][0]$ ，$dp[n?1][2][0]$ 中，且为三者的最大值。然而我们可以发现，由于在边界条件中 $dp[0][1][0]=dp[0][2][0]=0$ ，因此，$dp[n?1][1][0]$ ，$dp[n?1][2][0]$ 最终一定大于等于0。同时，如果最优的情况对应的是恰好一笔交易，那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，从$dp[n?1][1][0]$ 转移至$dp[n?1][2][0]$ ，因此最终的答案即为$dp[n?1][2][0]$

代码

时间复杂度为$O(n)$，空间复杂度为 $O(n)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[[0, 0], [0, 0], [0, 0]] for i in range(0, n)]

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

        for i in range(1, n):
	        # 今天买第一笔
            dp[i][1][1] = max(dp[i-1][1][1], -prices[i])  
            # 卖第一笔
            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]+prices[i]) 
            # 买第二笔 
            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0]-prices[i]) 
            # 卖第二笔 
            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1]+prices[i])  

        return dp[n-1][2][0]

空间优化

第 i 天的只与前一天的有关，而如果先更新了 dp[i][1][1] 再更新 dp[i][1][0]，在最大收益上与当天买入再卖出的最大收益相等（虽然并不符合题目说的最多两笔的要求，可以认为是当天买入再卖出不算做是一笔交易）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0, 0], [0, -prices[0]], [0, -prices[0]]]

        for i in range(1, n):
	        # 今天买第一笔
            dp[1][1] = max(dp[1][1], -prices[i])  
            # 卖第一笔
            dp[1][0] = max(dp[1][0], dp[1][1]+prices[i]) 
            # 买第二笔 
            dp[2][1] = max(dp[2][1], dp[1][0]-prices[i]) 
            # 卖第二笔 
            dp[2][0] = max(dp[2][0], dp[2][1]+prices[i])  

        return dp[2][0]

用 buy 和 sell 两组变量

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0

        for i in range(1, n):
            buy1 = max(buy1, -prices[i])  # 今天买第一笔
            sell1 = max(sell1, buy1+prices[i])  # 卖第一笔
            buy2 = max(buy2, sell1-prices[i])  # 买第二笔
            sell2 = max(sell2, buy2+prices[i])  # 卖第二笔

        return sell2

188. 买卖股票的最佳时机 IV

leetcode

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

• $0<=k<=100$
• $0<=prices.length<=1000$
• $0<=prices[i]<=1000$

思路

动态规划，可以在 III 的条件下进行拓展，新增的一维大小不再是 2 ，而是 k

定义状态转移数组 dp[天数][买入的次数][当前是否持股]

注意：同 III ，这里定义的是“买入的次数”

• 状态表达式：

  • $dp[i][k][1]$：第 $i$ 天结束时，进行了 $k$ 次交易且在操作后持有1份股票的情况下，最大收益
  • $dp[i][k][0]$：第 $i$ 天结束时，进行了 $k$ 次交易且在操作后持有0份股票的情况下，最大收益

• 状态转移方程：

  • 第 $i$ 天时，在完成 $k$ 笔交易和一次买操作的前提下不进行任何操作，保持不变；或者在完成 $k?1$ 笔交易的前提下以 $prices[i]$ 的价格买入股票（新的买入等于新增了一笔交易） d p [ i ] [ k ] [ 1 ] = m a x { d p [ i ? 1 ] [ k ] [ 1 ] , d p [ i ? 1 ] [ k ? 1 ] [ 0 ] ? p r i c e s [ i ] } dp[i][k][1]=max\{dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]\} dp[i][k][1]=max{dp[i?1][k][1],dp[i?1][k?1][0]?prices[i]}
  • 第 $i$ 天时，在完成 $k$ 笔交易的前提下不进行任何操作，保持不变；或者在完成 $k?1$ 笔交易和一次买操作的前提下以 $prices[i]$ 的价格卖出股票 d p [ i ] [ k ] [ 0 ] = m a x { d p [ i ? 1 ] [ k ] [ 0 ] , d p [ i ? 1 ] [ k ] [ 1 ] + p r i c e s [ i ] } dp[i][k][0]=max\{dp[i-1][k][0], dp[i-1][k][1]+prices[i]\} dp[i][k][0]=max{dp[i?1][k][0],dp[i?1][k][1]+prices[i]}

  即 { d p [ i ] [ k ] [ 1 ] = m a x { d p [ i ? 1 ] [ k ] [ 1 ] , d p [ i ? 1 ] [ k ? 1 ] [ 0 ] ? p r i c e s [ i ] } d p [ i ] [ k ] [ 0 ] = m a x { d p [ i ? 1 ] [ k ] [ 0 ] , d p [ i ? 1 ] [ k ] [ 1 ] + p r i c e s [ i ] } \left\{\begin{array}{l}dp[i][k][1]=max\{dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]\}\\dp[i][k][0]=max\{dp[i-1][k][0], dp[i-1][k][1]+prices[i]\}\end{array}\right. {dp[i][k][1]=max{dp[i?1][k][1],dp[i?1][k?1][0]?prices[i]}dp[i][k][0]=max{dp[i?1][k][0],dp[i?1][k][1]+prices[i]}?

• 初始化边界

  • $dp[0][k][1]=?prices[0]$：第0天买入
  • $dp[0][k][0]=0$：相当于第0天买入、卖出

• 返回值

  • $dp[n?1][k][0]$

因为 n 天最多进行 $?\frac{n}{2}?$ 笔交易（一天买，另一天卖），所以将 k 对$?\frac{n}{2}?$ 取最小值后动态规划

代码

时间复杂度 $O(nk)$，空间复杂度 $O(nk)$

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        k = min(k, n//2)
        dp = [[[0, -prices[0]] for j in range(k+1)] for i in range(n)]

        for i in range(1, n):
            for j in range(1, k+1):
                # 买入
                if j == 1:
                    # 第一笔
                    dp[i][j][1] = max(dp[i-1][j][1], -prices[i])
                else:
                    # 第二笔
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])

        return dp[n-1][k][0]

空间优化，时间复杂度 $O(nk)$，空间复杂度 $O(k)$

第 $i$ 天只依赖于 第 $i?1$ 天，可以用滚动数组取代 “天数” 的维度

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        k = min(k, n//2)
        dp = [[0, -prices[0]] for j in range(k+1)]
        
        for i in range(1,n):
            for j in range(1, k+1):
                # 买入
                if j==1:
                    # 第一笔
                    dp[j][1]=max(dp[j][1], -prices[i])
                else:
                    # 第二笔
                    dp[j][1]=max(dp[j][1], dp[j-1][0]-prices[i])
                dp[j][0]=max(dp[j][0],dp[j][1]+prices[i])

        return dp[k][0]

相当于是一维dp，用 buy 和 sell 两组变量

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        k = min(k, n//2)
        buy = [-prices[0]]*(k+1)
        sell = [0] * (k+1)
        for i in range(1, n):
            for j in range(1, k+1):
                if j == 1:
                    buy[j] = max(buy[j], -prices[i])
                else:
                    buy[j] = max(buy[j], sell[j-1]-prices[i])
                sell[j] = max(sell[j], buy[j]+prices[i])
        return sell[k]

309. 最佳买卖股票时机含冷冻期

leetcode

题目

给定一个整数数组$prices$，其中第 $prices[i]$ 表示第 $i$ 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

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

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

输入: prices = [1]
输出: 0

提示：

• $1<=prices.length<=5000$
• $0<=prices[i]<=1000$

思路

动态规划，在 II 的基础上进行改进

II 的状态转移方程：

• 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]}
• 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]}

结论：在第 $i?1$ 天卖出了股票，就不能在第 $i$ 天买入股票。因此，如果要在第 $i$ 天买入股票，$dp[i][1]$ 的状态转移方程中就不能使用 $dp[i?1][0]$，而应该使用 $dp[i?2][0]$。

分析：

• 如果第 $i$ 天买入股票，则第 $i?1$ 天不能卖出股票，根据 $dp[i][0]$ 的转移方程，取前一项，不取后一项，则 $dp[i?1][0]=dp[i?2][0]$，此时计算
  d p [ i ] [ 1 ] = m a x { d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] ? p r i c e s [ i ] } = m a x { d p [ i ? 1 ] [ 1 ] , d p [ i ? 2 ] [ 0 ] ? p r i c e s [ i ] } \begin{aligned}dp[i][1]&=max\{dp[i-1][1],dp[i-1][0]-prices[i]\}\\&=max\{dp[i-1][1],\textcolor{#DC5771}{dp[i-2][0]}-prices[i]\}\end{aligned} dp[i][1]?=max{dp[i?1][1],dp[i?1][0]?prices[i]}=max{dp[i?1][1],dp[i?2][0]?prices[i]}?
  状态表达式：

  • $dp[i][0]$：第 $i$ 天结束时，持有0份股票的情况下，最大收益
  • $dp[i][1]$：第 $i$ 天结束时，持有1份股票的情况下，最大收益

• 状态转移方程：
  - d p [ i ] [ 1 ] = m a x { d p [ i ? 1 ] [ 1 ] , d p [ i ? 2 ] [ 0 ] ? p r i c e s [ i ] } dp[i][1]=max\{dp[i-1][1], \textcolor{#DC5771}{dp[i-2][0]-prices[i]}\} dp[i][1]=max{dp[i?1][1],dp[i?2][0]?prices[i]}
  - 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]}

• 初始化边界

  • $dp[0][0]=0$ ：
  • $dp[0][1]=?prices[0]$：第0天买入

• 返回值：

  • $dp[n?1][0]$

代码

时间复杂度为$O(n)$，空间复杂度为 $O(n)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0, 0] for _ in range(n)]
        dp[0][1] = -prices[0]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])  
            # 第i天买入
            if i>=2:
                dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])  
            else:
                dp[i][1] = max(dp[i-1][1], -prices[i])  

        return dp[-1][0]

空间优化，时间复杂度为$O(n)$，空间复杂度为 $O(1)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp1 = -prices[0] # 持有1
        dp0 = dp2 =0    # 持有0，dp2：两天前持有0

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            newdp0 = max(dp0, dp1+prices[i])
            # 第i天买入
            newdp1 = max(dp1, dp2-prices[i]) # 原本应该是 max(dp1, dp0-prices[i])

            dp2 = dp0
            dp0 = newdp0 
            dp1 = newdp1

        return dp0

python 可以简写为

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp1 = -prices[0] # 持有1
        dp0 = dp2 =0    # 持有0，dp2：两天前持有0

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp0, dp1, dp2 = max(dp0, dp1+prices[i]), max(dp1, dp2-prices[i]), dp0

        return dp0

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

leetcode

题目

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

示例 2：

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

提示：

• $1<=prices.length<=5?104$
• $1<=prices[i]<5?10^4$
• $0<=fee<5?10^4$

思路

和 II 很相似，唯一的差别是每次交易都要付手续费，可以假设在买入的时候扣除手续费，可以假设在卖出的时候扣除手续费

新的状态转移方程有两种表示方法。

第一种表示方法，在每次买入股票时扣除手续费：

• d p [ i ] [ 1 ] = m a x { d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] ? p r i c e s [ i ] ? f e e } dp[i][1]=max\{dp[i-1][1], dp[i-1][0]-prices[i]-\textcolor{#DC5771}{fee}\} dp[i][1]=max{dp[i?1][1],dp[i?1][0]?prices[i]?fee}
• 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]}
• d p [ i ] [ 0 ] = m a x { d p [ i ? 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] + p r i c e s [ i ] ? f e e } dp[i][0]=max\{dp[i-1][0], dp[i-1][1]+prices[i]-\textcolor{#DC5771}{fee}\} dp[i][0]=max{dp[i?1][0],dp[i?1][1]+prices[i]?fee}

代码

时间复杂度为$O(n)$，空间复杂度为 $O(n)$

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0, 0] for _ in range(n)]
        dp[0][1] = -prices[0]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee)  
            # 第i天买入
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])  

        return dp[-1][0]

时间复杂度为$O(n)$，空间复杂度为 $O(1)$

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [0, -prices[0]]

        for i in range(1, n):  # 从1开始遍历
	        # 第i天卖掉
            dp[0] = max(dp[0], dp[1]+prices[i]-fee) 
            # 第i天买入
            dp[1] = max(dp[1], dp[0]-prices[i])

        return dp[0]