核心思想

用狀態(tài)機(jī)模型求解動(dòng)態(tài)規(guī)劃問題，就是將原始問題用狀態(tài)機(jī)模型進(jìn)行表示，即每個(gè)節(jié)點(diǎn)表示狀態(tài)，每條邊表示一個(gè)狀態(tài)轉(zhuǎn)移，邊上的權(quán)值表示轉(zhuǎn)移的代價(jià)或收益。

狀態(tài)機(jī)模型的目標(biāo)是找到一條從初始狀態(tài)出發(fā)，經(jīng)過若干次狀態(tài)轉(zhuǎn)移，達(dá)到某個(gè)終止?fàn)顟B(tài)的路徑，使得最終的結(jié)果值最大或最小。

LeetCode-198. 打家劫舍

題目描述

原題鏈接

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

問題分析

狀態(tài)定義：

• dp[i][0]：表示不偷竊第 i 家，前 i 家的最大收益。
• dp[i][1]：表示偷竊第 i 家，前 i 家的最大收益。

狀態(tài)轉(zhuǎn)移：

• 若不偷竊第 i 家，則可以從dp[i-1][0]或dp[i-1][0]轉(zhuǎn)移過來，即dp[i][0] = max(dp[i-1][0], dp[i-1][1])
• 若偷竊第 i 家，因?yàn)椴荒芡蹈`兩間相鄰的房屋，因此dp[i][1]只能從第 i-1 家沒有被偷竊的狀態(tài)轉(zhuǎn)移過來，即dp[i][1] = dp[i-1][0] + nums[i]

對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移圖如下：

狀態(tài)壓縮

觀察上述狀態(tài)壓縮圖，我們可以進(jìn)一步將狀態(tài)壓縮到只有兩個(gè)狀態(tài)：

壓縮后的狀態(tài)轉(zhuǎn)移方程：

• dp[0] = max(dp[0], dp[1])
• dp[1] = dp[0] + nums[i]

復(fù)雜度分析

時(shí)間復(fù)雜度為：$O(n)$

空間復(fù)雜度為：$O(1)$

程序代碼

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(2, 0);
        dp[1] = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            int t = dp[0];
            dp[0] = max(dp[0], dp[1]);
            dp[1] = t + nums[i];
        }
        return max(dp[0], dp[1]);
    }
};

LeetCode-188. 買賣股票的最佳時(shí)機(jī) Ⅳ

題目描述

原題鏈接

給你一個(gè)整數(shù)數(shù)組 prices 和一個(gè)整數(shù) k ，其中 prices[i] 是某支給定的股票在第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 k 筆交易。也就是說，你最多可以買 k 次，賣 k 次。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

問題分析

我們將股票買入記為一次新的交易的開始。

狀態(tài)定義：

• dp[i][j][0]：第 i 天，正在進(jìn)行第 j 次交易，手中沒有持有股票
• dp[i][j][1]：第 i 天，正在進(jìn)行第 j 次交易，手中持有股票

狀態(tài)轉(zhuǎn)移：

• 若第 i 天，正在進(jìn)行第 j 次交易，手中沒有持有股票，則上一天可能正在進(jìn)行第 j 次交易，且手中沒有持有股票?；蛘呱弦惶斐钟泄善?，并在第 i 天賣出，即dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
• 若第 i 天，正在進(jìn)行第 j 次交易，手中持有股票，則上一天可能正在進(jìn)行第 j 次交易，且手中沒有持有股票。或者上一天不持有股票，并在第 i 天買入，即dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

狀態(tài)轉(zhuǎn)移圖：

狀態(tài)壓縮

上述的狀態(tài)轉(zhuǎn)化圖可以進(jìn)一步壓縮：

壓縮后的狀態(tài)轉(zhuǎn)移方程：

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

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(n\times k)$

空間復(fù)雜度：$O(2\times k)$

程序代碼

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(k+1, vector<int>(2, 0));
        
        for(int i = 1; i <= k; i++)  dp[i][1] = -prices[0];

        for(int i = 1; i < prices.size(); i++) {
            for(int j = k; j >= 1; j--) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]);
            }
        }

        return dp[k][0];
    }
};

LeetCode-309. 買賣股票的最佳時(shí)機(jī)含冷凍期

題目描述

給定一個(gè)整數(shù)數(shù)組prices，其中第 prices[i] 表示第 _i_ 天的股票價(jià)格 。?

設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

• 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

問題分析

我們將股票買入記為一次新的交易的開始。

狀態(tài)定義：

• dp[i][0]：第 i 天，手中沒有持有股票第 1 天。
• dp[i][1]：第 i 天，手中沒有持有股票超天數(shù)大于等于 2。
• dp[i][2]：第 i 天，手中持有股票。

狀態(tài)轉(zhuǎn)移：

• dp[i][0] = dp[i-1][2] + prices[i]：第 i 天，手中沒有持有股票第一天，一定是第 i -1 天持有股票，并在第 i 天賣出。
• dp[i][1] = max(dp[i-1][1], dp[i-1][0])：第 i 天，手中沒有持有股票天數(shù)大于等于 2。則上一狀態(tài)可能是不持有股票天數(shù)大于等于 2（dp[i-1][1]）或第 i -1 天是不持有股票第一天（dp[i-1][0]）。
• dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i])：第 i 天，正在進(jìn)行第 j 次交易，手中持有股票。則上一狀態(tài)可能是持有股票（dp[i-1][2]）或第 i-1 天不持有股票天數(shù)大于等于2，并在第 i 天買入股票，即dp[i-1][1] - prices[i]。

狀態(tài)轉(zhuǎn)移圖：

狀態(tài)壓縮

上述狀態(tài)機(jī)模型圖可以進(jìn)一步壓縮：

壓縮后的狀態(tài)轉(zhuǎn)移方程：

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

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(n)$

空間復(fù)雜度：$O(1)$文章來源地址http://www.zghlxwxcb.cn/news/detail-835259.html

程序代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(3, 0);

        dp[2] = -prices[0];

        for(int i = 1; i < n; i++) {
            int t0 = dp[0], t1 = dp[1], t2 = dp[2];
            dp[0] = t2 + prices[i];
            dp[1] = max(t0, t1);
            dp[2] = max(t1 - prices[i], t2);
        }

        return max(dp[0], dp[1]);
    }
};

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃系列 | 狀態(tài)機(jī)模型（上）| 練完這些就算入門了！的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！