目錄

動(dòng)態(tài)規(guī)劃怎么學(xué)？

1. 題目解析

2. 算法原理

1. 狀態(tài)表示

2. 狀態(tài)轉(zhuǎn)移方程

3. 初始化

4. 填表順序

5. 返回值

3. 代碼編寫(xiě)

寫(xiě)在最后：

動(dòng)態(tài)規(guī)劃怎么學(xué)？

學(xué)習(xí)一個(gè)算法沒(méi)有捷徑，更何況是學(xué)習(xí)動(dòng)態(tài)規(guī)劃，

跟我一起刷動(dòng)態(tài)規(guī)劃算法題，一起學(xué)會(huì)動(dòng)態(tài)規(guī)劃！

1. 題目解析

題目鏈接：188. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV - 力扣（LeetCode）?

這道題跟上一道題是一模一樣啊，我的評(píng)價(jià)是，當(dāng)一個(gè) CV 工程師，

我馬上 CV 出結(jié)果：

上一題的代碼：

這一題的代碼：

?雖然話(huà)是這么說(shuō)，我們還是再做一遍這道題：

2. 算法原理

1. 狀態(tài)表示

dp[ i ] 表示到第 i 天的時(shí)候，所能獲得的最大利潤(rùn)，

實(shí)際上，我們還是可以將他分成兩種情況：

買(mǎi)入狀態(tài)和可交易狀態(tài)，而且我們需要記錄完成了幾次交易

f [ i ][ j ] 表示第 i 天結(jié)束之后，完成了 j 次交易，處于 “買(mǎi)入” 狀態(tài)的最大利潤(rùn)，

g [ i ][ j ] 表示第 i 天結(jié)束之后，完成了 j 次交易，處于 “可交易” 狀態(tài)的最大利潤(rùn)，

這里再次說(shuō)明，買(mǎi)入狀態(tài)指的是手里有股票，

而可交易狀態(tài)表示的是手里沒(méi)有股票。

2. 狀態(tài)轉(zhuǎn)移方程

我們先從 f?[ i ][ j ] 開(kāi)始分析，就兩種情況，一種是昨天是買(mǎi)入，一種是昨天是可交易狀態(tài)，

買(mǎi)入狀態(tài)啥也不干就行，可交易狀態(tài)只要在今天買(mǎi)入就能進(jìn)入買(mǎi)入狀態(tài)，所以：

f [ i ][ j ] = max( f [ i - 1 ][ j ]，g [ i - 1 ][ j ] - p [ i ] )

然后是 g [ i ][ j ] ，也是同樣的兩種情況，

如果是買(mǎi)入狀態(tài)就賣(mài)出，當(dāng)天的 j 是比現(xiàn)在小1的，如果是可交易狀態(tài)，就啥也不干就行，所以：

g [ i ][ j ] = max( g[ i - 1 ][ j ]，f [ i -?1 ][ j - 1?] + p [ i ]?)

3. 初始化

為了防止越界，我們需要對(duì)他進(jìn)行一些特殊的處理，

然后為了防止前面的值影響后面的值，我們需要把數(shù)組內(nèi)容初始化成負(fù)無(wú)窮大

然后把 f [ 0?][ 0 ] = -p[ 0 ]，讓 g [ 0 ][ 0 ] = 0 即可

4. 填表順序

從上往下，從左往右，兩個(gè)表一起填

5. 返回值

g 表最后一行的最大值

3. 代碼編寫(xiě)

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < k + 1; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j > 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ans = 0;
        for(auto e : g[n - 1]) ans = max(ans, e);
        return ans;
    }
};

寫(xiě)在最后：

以上就是本篇文章的內(nèi)容了，感謝你的閱讀。

如果感到有所收獲的話(huà)可以給博主點(diǎn)一個(gè)贊哦。

如果文章內(nèi)容有遺漏或者錯(cuò)誤的地方歡迎私信博主或者在評(píng)論區(qū)指出~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-645843.html

到了這里，關(guān)于【學(xué)會(huì)動(dòng)態(tài)規(guī)劃】買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV（18）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！