leetcode-动态规划【股票问题】_股票问题leetcode

目录

121. 买卖股票的最佳时机（只能买卖一次）

122. 买卖股票的最佳时机ii （可以买卖多次）

123. 买卖股票的最佳时机iii （最多买卖两次）

188. 买卖股票的最佳时机iv （最多买卖k次）

309. 最佳买卖股票时机含冷冻期（买卖多次，卖出有一天冷冻期）

714. 买卖股票的最佳时机含手续费（买卖多次，每次有手续费）

---

1. 用dp[i][0]表示第i天持有股票所得最多现金，dp[i][1]表示第i天不持有股票所得最多现金。

2. 确定递推公式

第i天持有股票所得最多现金dp[i][0]， 可以由两个状态推出来

• 第i-1天持有股票：dp[i - 1][0]
• 第i天买入股票：-prices[i]

dp[i][0] = max(dp[i - 1][0], -prices[i]);

第i天不持有股票所得最多现金dp[i][1]， 也可以由两个状态推出来

• 第i-1天就不持有股票：dp[i - 1][1]
• 第i天卖出股票：dp[i - 1][0] + prices[i]

dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

3. 初始化dp数组：dp[0][0] -= prices[0]，dp[0][1] = 0

121. 买卖股票的最佳时机（只能买卖一次）

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n < 2:
            return 0
        profit = 0
        # 存储第i天卖出时的最低买入价
        dp = [0 for _ in range(n)]
        dp[0] = prices[0]
        for i in range(1, n):
            dp[i] = min(dp[i-1], prices[i])
            profit = max(profit, prices[i]-dp[i])
        return profit

# 按照公式流程
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2: return 0
        # dp[i][0]存储第i天持有股票所得最多现金
        # dp[i][1]存储第i天不持有股票所得最多现金
        dp = [[-prices[0], 0]]
        for i in range(1, len(prices)):
            # dp[i-1][0]：第i-1天买入/持有，第i天继续持有
            # -prices[i]：第i天买入
            res0 = max(dp[i-1][0], -prices[i])
            # dp[i-1][1]：第i-1天非持有，第i天继续非持有
            # dp[i-1][0]+prices[i]：第i天卖出
            res1 = max(dp[i-1][1], dp[i-1][0]+prices[i])
            dp.append([res0, res1])
        return dp[-1][1]

122. 买卖股票的最佳时机ii （可以买卖多次）

# 贪心算法
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        ans = 0
        pre = prices[0]
        for i in range(len(prices)):
            if prices[i] > pre:
                ans += prices[i] - pre
            pre = prices[i]
        return ans

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # res0持有，res1不持有
        dp = [[-prices[0], 0]]
        for i in range(1, len(prices)):
            # dp[i-1][0]：第i-1天买入/持有，第i天继续持有
            # dp[i-1][1]-prices[i]：第i天买入 + 之前买卖的利润
            res0 = max(dp[i - 1][0], dp[i-1][1]-prices[i])
            # dp[i-1][1]：第i-1天非持有，第i天继续非持有
            # dp[i-1][0]+prices[i]：第i天卖出
            res1 = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
            dp.append([res0, res1])
        return dp[-1][1]

123. 买卖股票的最佳时机iii （最多买卖两次）

dp[i][j]表示第i天的第j个状态所持有的最大现金，每天有5个状态：

0：没有操作

1：第一次买入/持有：dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1])

2：第一次卖出：dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

3：第二次买入/持有：dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])

4：第二次卖出：dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

初始化：dp[0] = [0, -prices[0], 0, -prices[0], 0]，注意这里dp[0][3]相当于在第一天买入卖出后又买入了一次，所以应该是 -prices[0]

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 0:没有操作
        # 1:第一次买入/持有
        # 2:第一次卖出
        # 3:第二次买入/持有
        # 4:第二次卖出
        dp = [[0, -prices[0], 0, -prices[0], 0]]
        for i in range(1, len(prices)):
            res0 = dp[i-1][0]
            res1 = max(dp[i-1][1], dp[i-1][0] - prices[i])
            res2 = max(dp[i-1][2], dp[i-1][1] + prices[i])
            res3 = max(dp[i-1][3], dp[i-1][2] - prices[i])
            res4 = max(dp[i-1][4], dp[i-1][3] + prices[i])
            dp.append([res0, res1, res2, res3, res4])
        return dp[-1][-1]

188. 买卖股票的最佳时机iv （最多买卖k次）

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k == 0 or len(prices) < 2: return 0
        # 0:没有操作
        # 1:第一次买入/持有
        # 2:第一次卖出
        # ...
        # 2k-1:第k次买入/持有
        # 2k:第k次卖出
        dp = [[0 for _ in range(2*k+1)] for _ in range(len(prices))]
        for j in range(1, 2*k, 2):
            dp[0][j] = -prices[0]
        for i in range(1, len(prices)):
            for j in range(0, 2 * k - 1, 2):
                # 买入/持有
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i])
                # 卖出/非持有
                dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i])
        return dp[-1][-1]

309. 最佳买卖股票时机含冷冻期（买卖多次，卖出有一天冷冻期）

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # dp[持有，非持有]
        dp = [[0, 0] for _ in range(len(prices))]
        dp[0] = [-prices[0], 0]
        for i in range(1, len(prices)):
            if i == 1:
                dp[i][0] = max(dp[i - 1][0], -prices[i])
            else:
                dp[i][0] = max(dp[i - 1][0], dp[i - 2][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
        return dp[-1][-1]

714. 买卖股票的最佳时机含手续费（买卖多次，每次有手续费）

class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        dp = [[0,0] for _ in range(len(prices))]
        dp[0] = [-prices[0], 0]
        for i in range(1, len(prices)):
            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] - fee)
        return dp[-1][-1]