?

步驟一、確定狀態(tài):

確定dp數(shù)組及下標(biāo)含義 dp[i]是一個長度為len(prices)的一維數(shù)組，表示的是在第i天持有股票

步驟二、推斷狀態(tài)方程:

第i天持有股票，即dp[i][1], 那么兩個狀態(tài):

1、第i-1天就持有股票， 保持現(xiàn)狀過來的， 最大利潤就是昨天持有股票的最 大利潤dp[i-1][1]

2、第i-1天沒有股票，第i天剛買進(jìn)來的， 那這時候的最大利潤就是dp[i- 1][0]-prices[i]，注意這個不是僅僅的-prices[i]了， 因?yàn)榇藭r可以進(jìn)行多次 交易了， 即使第i-1沒有股票，那么也可能會有更前面的利潤傳過來，dp[i][1] 選擇最大的: dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])

步驟四、計算順序:

從左往右， 從1開始遍歷，返回的是最后沒有股票時候的最大利潤， 也就是dp[-1][0]

class Solution:def maxProfit(self, prices: List[int]) -> int:# 異常值判斷if len(prices) < 2:return 0# dp數(shù)組定義dp = [[0,0] for _ in range(len(prices))]# dp初始化dp[0][0] = 0dp[0][1] = -prices[0]for i in range(1, len(prices)):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]) # 第i天持有股票return dp[-1][0]

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的106. Leetcode 122. 买卖股票的最佳时机 II (动态规划-股票交易)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。