121. 買賣股票的最佳時機

方法1：貪心思路

但是利用其他思路只能解決具體場景下的問題，并不能解決通用的一些問題。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = 0
        maxPrice = -float("inf")
        for i in range(1,len(prices)):
            if prices[i] - prices[buy] <= 0:
                # 以更低的價格買入
                buy = i
                continue
            elif prices[i] - prices[buy] > maxPrice:
                maxPrice = prices[i] - prices[buy]
        return maxPrice if maxPrice >=0 else 0

方法2：動態(tài)規(guī)劃

1. dp[i][0] ：表示第i天持有該股票的最大收益，dp[i][1] 表示第i天不持有該股票的最大收益。需要注意的是第i天的情況是什么樣，并不是表示第i天就賣出了這只股票，而是表示
2. 遞推公式： dp[i][0]
   第一種是保持i-1天的狀態(tài)不變，dp[i-1][0]
   第二種是買入這支股票手里的剩余金額 -prices[i]
   前一天保持不持有的狀態(tài)，或者今天賣出了股票，這是后一天情況依賴于前面情況的關系。
   dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
3. dp[0][0]=-prices 和 dp[1][0]=0
4. 遍歷方式： 后面的狀態(tài)依賴于前面的狀態(tài)，所以需要遍歷每一天的數(shù)值。
5. 打印dp數(shù)組

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

122.買賣股票的最佳時機II

方法1：貪心算法

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

方法2：動態(tài)規(guī)劃

區(qū)別： 股票可以買賣多次，這個時候的最大利潤是多少。僅僅在遞推公式和買賣股票I有所不同，其他代碼均相同。文章來源地址http://www.zghlxwxcb.cn/news/detail-481424.html

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        dp = [[0,0] for _ in range(N)]
        dp[0][0] = -prices[0] 
        dp[0][1] = 0
        for i in range(1,N):
            # 0表示不持有該股票；1表示持有該股票
            # 如果不持有該股票，一種情況是買入，另一種情況是繼續(xù)保持不持有的狀態(tài)
            # 如果當前是持有該股票的狀態(tài)，一種情況是賣出，另一種情況是繼續(xù)保持之前的持有狀態(tài)，不賣出
            dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0])
            dp[i][1] = max(dp[i-1][1],dp[i-1][0] + prices[i])
        return max(dp[N-1][0],dp[N-1][1]) 

到了這里，關于day49-動態(tài)規(guī)劃10-買賣股票問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！