国庆四天，Leetcode 的每日一题回归了动态规划的典型题目：买卖股票。

买卖股票1

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

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

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

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=daily-question&envId=2023-10-01

code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 一次交易
        cost = float('inf') # 确保获得最小的价格
        profit = 0
        for i in prices:
            cost = min(cost, i) # 保证我是低价买进来的
            profit = max(profit, i - cost)  # 1，跟着后面进行更新保证先有 cost，后有 profit；2，max(我就不卖，我卖掉了后获得的利润=今天的价格-我买入时候的价格)
        return profit

买卖股票2

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

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/?envType=daily-question&envId=2023-10-02

code：

前面学了差分，想用起来：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)  # 获取价格数组的长度
        if n == 0:  # 如果价格数组为空，则返回0
            return 0

        # 计算相邻两天的价格差
        diff = [prices[i] - prices[i - 1] for i in range(1, n)]
        profit = 0  # 初始化利润为0

        for i in range(len(diff)):  # 遍历价格差数组
            if diff[i] > 0:  # 如果价格差为正（即价格上升）
                profit += diff[i]  # 将价格差累加到利润中

        return profit  # 返回总利润

动态规划：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

    	# 初始化两种状态的利润
        hold, notHold = -prices[0], 0
        
        for i in range(len(prices)):
        	# 更新持有股票状态的利润
            hold = max(hold, notHold - prices[i])
        	# 更新不持有股票状态的利
            notHold = max(notHold, hold + prices[i])
        return notHold

买卖股票3

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

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

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

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/?envType=daily-question&envId=2023-10-03

code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[[0, float('-inf')] for _ in range(3)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, 3):
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1])
        return max(dp[n][j][0] for j in range(3))

优化后 code：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]  # 初始化第一次买入的成本
        sell1 = sell2 = 0  # 初始化第一次和第二次卖出的利润为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])  # 第二次卖出的最大利润
            print(buy1,sell1,buy2,sell2)
        return sell2  # 返回第二次卖出后的最大利润

买卖股票4

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

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

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/?envType=daily-question&envId=2023-10-04

code:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        dp = [[[0, float('-inf')] for _ in range(k + 1)] for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, k + 1):
                # 今天没有股票：可能是昨天也没有股票，或者昨天有股票但今天卖了
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1])
                # 今天有股票：可能是昨天也有股票，或者昨天没有股票但今天买了
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1])

        return max(dp[n][j][0] for j in range(k + 1))

国际站高投票答案，加了注释：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        def quickSolve(prices):  # 快速解决在交易次数足够多的情况
            return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))
        
        len_prices = len(prices)  # 获取价格数组的长度
        if k >= len_prices // 2:  # 如果交易次数足够多，调用quickSolve函数
            return quickSolve(prices)
        
        t = [[0] * len_prices for _ in range(k + 1)]  # 初始化动态规划表
        for i in range(1, k + 1):  # 遍历交易次数
            tmpMax = -prices[0]  # 初始化临时最大值
            for j in range(1, len_prices):  # 遍历天数
                t[i][j] = max(t[i][j - 1], prices[j] + tmpMax)  # 更新卖出的最大利润
                tmpMax = max(tmpMax, t[i - 1][j - 1] - prices[j])  # 更新买入的最大利润
        
        return t[k][len_prices - 1]  # 返回最终的最大利润