??思維導(dǎo)圖整理大廠面試高頻數(shù)組19: 股票問題III的dp數(shù)組構(gòu)建/初始化和空間優(yōu)化難點(diǎn), 力扣1

劉福發(fā)布于2021-10-11 10:59 / 1933人閱讀

此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解.

目的是為了更方便快捷的記憶和回憶算法重點(diǎn)(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進(jìn)一步加強(qiáng)理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號(hào)先去力扣看看官方題解, 然后再看本文內(nèi)容).

關(guān)于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點(diǎn)/技巧, 以及思維導(dǎo)圖源文件問題請(qǐng)點(diǎn)擊此鏈接.

想進(jìn)大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法, 博主同步更新了算法視頻講解和其他文章/導(dǎo)圖講解, 更易于理解, 歡迎來看!

關(guān)注博主獲得題解更新的最新消息!!!

文章目錄

0.導(dǎo)圖整理
1.dp數(shù)組的構(gòu)建
2.確定遞推公式
3.dp數(shù)組如何初始化
4.最終返回結(jié)果
5.空間優(yōu)化的解釋
源碼
Python:
java:

題目鏈接: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/si-wei-dao-tu-zheng-li-dpshu-zu-gou-jian-csyk/

0.導(dǎo)圖整理

1.dp數(shù)組的構(gòu)建

本題最難的地方就在于 dp數(shù)組的構(gòu)建了, 因?yàn)樗幌袂懊嬷v過的兩道股票問題那樣, dp數(shù)組只需要用兩種狀態(tài)就可以表示了: 當(dāng)天持有/不持有股票. 本題由于加了 最多買賣兩次 的條件, 使問題一下子就變得復(fù)雜了, 用之前的兩種狀態(tài)并不能體現(xiàn) 最多買賣兩次的限制, 所以我們需要重新設(shè)計(jì)dp數(shù)組.

用上圖中的五種狀態(tài)就可以完美地體現(xiàn)出最多買賣兩次的限制, 然后經(jīng)過分析可以看出第一種狀態(tài)利潤為0, 對(duì)結(jié)果沒什么影響, 所以我們最終只要定義剩下的4個(gè)狀態(tài)即可. 定義dp數(shù)組的名稱還是一貫地采用比較容易識(shí)別的名稱, 這比那些用到二維dp數(shù)組, 甚至有些題解用到了三維dp數(shù)組要好多了.

2.確定遞推公式

定義出了dp數(shù)組之后, 按照前面兩題的經(jīng)驗(yàn), 遞推公式就沒太大難度了, 還是每種狀態(tài)都由兩種情況組合而來, 最終取最大值:

3.dp數(shù)組如何初始化

本題的初始化也有一定難度, 畢竟dp數(shù)組實(shí)在太多了.

先來明確下題目中的隱含條件: 無論題目中是否允許「在同一天買入并且賣出」這一操作, 最終的答案都不會(huì)受到影響, 這是因?yàn)?strong>這一操作帶來的收益為零, 所以為了方便初始化, 這里默認(rèn)是可以的. 于是就有了下面的初始化過程:

如果題目不允許的話, 那初始化就會(huì)稍微麻煩一些了, 比如sell1[i]就只能在第二天進(jìn)行sell1[1]的初始化了, 同理: buy2[i]在第三天進(jìn)行buy2[2]的初始化, sell2[i]在第四天進(jìn)行sell2[3]的初始化, 這就是能否「在同一天買入并且賣出」的不同之處.

4.最終返回結(jié)果

在動(dòng)態(tài)規(guī)劃結(jié)束后,由于我們可以進(jìn)行不超過兩筆交易,因此最終的答案在0,sell1[i],sell2[i]中, 且為三者中的最大值, 由于在邊界條件中sell1[i],sell2[i]的值已經(jīng)為0, 并且在狀態(tài)轉(zhuǎn)移的過程中我們維護(hù)的是最大值, 因此sell1[i],sell2[i]最終一定大于等于0.

同時(shí), 如果最優(yōu)的情況對(duì)應(yīng)的是恰好一筆交易, 那么它也會(huì)因?yàn)槲覀冊(cè)谵D(zhuǎn)移時(shí)允許在同一天買入并且賣出這一寬松的條件, 從sell1[i]轉(zhuǎn)移至sell2[i], 可以理解假如最優(yōu)是 sell1[i] 的話, 可以當(dāng)天再做一次買賣, 也就是完成兩次交易, 所以無論如何都可以是 sell2[i] 最優(yōu).

5.空間優(yōu)化的解釋

代碼在空間優(yōu)化上和我們之前說過的直接將數(shù)組用變量來替換就可以了, 但是它在理解上還是有一定難度的.

例如在計(jì)算sell1[i]時(shí), 我們直接使用buy1[i]而不是buy1[i-1]進(jìn)行轉(zhuǎn)移。buy1[i]比 buy[i-1]多考慮的是在第i天買入股票的情況, 而轉(zhuǎn)移到sell1[i]時(shí), 考慮的是在第i天賣出股票的情況, 這樣在同一天買入并且賣出收益為零, 不會(huì)對(duì)答案產(chǎn)生影響, 所以我們才能這樣進(jìn)行優(yōu)化.

源碼

Python:

## 未進(jìn)行空間優(yōu)化class Solution:    def maxProfit(self, prices: List[int]) -> int:        n = len(prices)        buy1 = [0] * n        sell1 = [0] * n        buy2 = [0] * n        sell2 = [0] * n        buy1[0] = buy2[0] = -prices[0]        sell1[0] = sell2[0] = 0        for i in range(1, n):            buy1[i]  = max(buy1[i-1], -prices[i])            sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])            buy2[i]  = max(buy2[i-1], sell1[i-1] - prices[i])            sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])        return sell2[-1]## 空間優(yōu)化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

java:

//未進(jìn)行空間優(yōu)化class Solution {    public int maxProfit(int[] prices) {        int n = prices.length;        int[] buy1 = new int[n];        int[] sell1 = new int[n];        int[] buy2 = new int[n];        int[] sell2 = new int[n];        buy1[0] = -prices[0]; sell1[0] = 0;        buy2[0] = -prices[0]; sell2[0] = 0;        for (int i = 1; i < n; ++i) {            buy1[i]  = Math.max(buy1[i-1], -prices[i]);            sell1[i] = Math.max(sell1[i-1], buy1[i-1] + prices[i]);            buy2[i]  = Math.max(buy2[i-1], sell1[i-1] - prices[i]);            sell2[i] = Math.max(sell2[i-1], buy2[i-1] + prices[i]);        }        return sell2[n-1];    }}