摘要

• 有些動(dòng)態(tài)規(guī)劃的題目的難點(diǎn)在于如何劃分狀態(tài)和這些狀態(tài)之間如何進(jìn)行轉(zhuǎn)移吹埠，列出可能的狀態(tài)以及轉(zhuǎn)移到這些狀態(tài)的可能，是定義dp數(shù)組及數(shù)組下標(biāo)、推導(dǎo)遞推公式的關(guān)鍵藻雌。

• 畫出簡(jiǎn)單的狀態(tài)轉(zhuǎn)移示意圖雌续，有助于清楚地劃分狀態(tài)以及模擬狀態(tài)轉(zhuǎn)移的過程，對(duì)如何定義dp數(shù)組以及推導(dǎo)狀態(tài)轉(zhuǎn)移方程有一定啟發(fā)胯杭。

• 對(duì)于初始化中的非法狀態(tài)驯杜，不要死摳dp數(shù)組的定義，只要初始值能讓遞推公式能正確計(jì)算即可做个。

• 有一部分可以使用動(dòng)態(tài)規(guī)劃解決的問題鸽心，如果問題具有貪心選擇性質(zhì)，也可以用貪心法解決居暖，貪心法是動(dòng)態(tài)規(guī)劃的特例顽频，貪心法的效率往往比動(dòng)態(tài)規(guī)劃要高。而動(dòng)態(tài)規(guī)劃往往是一類問題的通解太闺，代碼的復(fù)用性和可擴(kuò)展性更好糯景。

LeetCode309 最佳買賣股票的時(shí)機(jī)含冷凍期

309. 最佳買賣股票時(shí)機(jī)含冷凍期 - 力扣（Leetcode）

• 這道題目添加了“冷凍期”這個(gè)規(guī)則，需要更精細(xì)地劃分每一天的狀態(tài)省骂。

  • 首先蟀淮，本題不限制買賣股票地次數(shù)，所以不需要記錄每天買賣股票的次數(shù)钞澳。但要先買入股票才能賣出股票怠惶，至少需要記錄每天是否持有股票。

  • 但由于“冷凍期”的限制轧粟，不能再賣出股票后的第二天買入股票策治，所以賣出股票的第二天一定不能持有股票，這和其他時(shí)候沒有持有股票的是不一樣的兰吟。非“冷靜期”時(shí)可以選擇是否買入股票粟焊，而“冷靜期”時(shí)不能選擇買入股票湖蜕。都是不持有股票汰具，但應(yīng)該區(qū)分冷靜期和非冷靜期桨醋。

  • 對(duì)一天的狀態(tài)嘗試進(jìn)行劃分，一天可能有如下4種狀態(tài)

    1. 今天持有股票
    2. 今天賣出股票
    3. 今天是冷凍期拄丰，不能買入股票
    4. 今天不是冷凍期府树，且未持有股票

  • 然后要分析這些狀態(tài)相互之間如何進(jìn)行轉(zhuǎn)移

    • 今天持有股票：
      1. 前一天持有股票且不賣出，那今天也是持有股票
      2. 前一天賣出了股票料按，今天是冷凍期奄侠，不能買入股票
      3. 前一天是冷凍期，那今天正好可以買入股票载矿，今天買入股票
      4. 前一天不是冷凍期且未持有股票垄潮，那今天買入股票
    • 今天賣出股票
      1. 前一天一定要持有股票烹卒，今天才能賣出
    • 今天是冷凍期
      1. 只有前一天賣出了股票，今天才會(huì)是冷凍期
    • 今天不是冷凍期弯洗，且未持有股票
      1. 前一天是冷凍期旅急，今天正好解凍，但是今天不買入股票
      2. 前一天不是冷凍期牡整，也未持有股票藐吮，今天不買入股票

  • 可以得到這樣的狀態(tài)轉(zhuǎn)移圖

image.png

• 確定dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]為到第i天時(shí)能獲得的最大金額，j代表第i天處于什么狀態(tài)：j==0為“今天持有股票”逃贝，j==1為“今天賣出股票”谣辞，j==2為“今天是冷靜期”，j==3為“今天不是冷靜期且未持有股票”沐扳。

• 確定狀態(tài)轉(zhuǎn)移方程泥从，根據(jù)之前對(duì)狀態(tài)轉(zhuǎn)移的分析

  • 今天持有股票，dp[i][0]
    1. 前一天持有股票且不賣出沪摄，那今天也是持有股票
    2. 前一天賣出了股票躯嫉，今天是冷凍期，不能買入股票杨拐，不能轉(zhuǎn)移到這個(gè)狀態(tài)
    3. 前一天是冷凍期和敬，那今天正好可以買入股票，今天買入股票
    4. 前一天不是冷凍期且未持有股票戏阅，那今天買入股票
  • 今天賣出股票
    1. 前一天一定要持有股票，今天才能賣出
  • 今天是冷靜期
    1. 只有前一天賣出了股票啤它，今天才會(huì)是冷凍期
  • 今天不是冷靜期且未持有股票
    1. 前一天是冷凍期奕筐，今天正好解凍，但是今天不買入股票
    2. 前一天不是冷凍期变骡，也未持有股票离赫，今天不買入股票

• 確定初始狀態(tài)，初始化dp數(shù)組塌碌，假設(shè)初始金額為0

  • 第0天持有股票就是第0天買入渊胸，dp[0][0]=0-prices[i]
  • 第0天賣出股票，看成第0天買入再賣出（雖然題目不允許這樣）台妆，也可以看成是為了要正確計(jì)算下一天處于冷靜期時(shí)的dp值翎猛，dp[0][1]應(yīng)該初始化成0。dp[0][1]=0
  • 第0天是冷靜期接剩，看成第0天買入再賣出切厘，第0天也不允許再進(jìn)行買賣了，也可以看成是為了要正確計(jì)算下一天未持有股票的dp值懊缺，dp[0][2]應(yīng)該初始化成0疫稿。dp[0][2]=0
  • 第0天不是冷靜期且未持有股票，實(shí)際上就是第0天什么也不做，dp[0][3]=0

• 每天的各個(gè)狀態(tài)的更新都依賴于上一天的狀態(tài)遗座，所以i應(yīng)該從小到大遍歷舀凛。

題解代碼如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
        dp[0][0] = 0 - prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;

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

        return max(dp[prices.size() - 1][1], max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));
    }
};

• 最后肯定是手上未持有股票時(shí)，持有的金額最大途蒋，而未持有股票實(shí)際上就對(duì)應(yīng)著下標(biāo)j為[1-3]的狀態(tài)猛遍，從這三種中去最大值即可。

LeetCode714 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

714. 買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi) - 力扣（Leetcode）

• 這道題目和 122. 買賣股票的最佳時(shí)機(jī) II - 力扣（Leetcode） 也只是在遞推公式上有區(qū)別碎绎，遞推公式中需要加入手續(xù)費(fèi)的計(jì)算螃壤。在 代碼隨想錄算法訓(xùn)練營(yíng)打卡Day49 中，已經(jīng)用動(dòng)態(tài)規(guī)劃的思路較詳細(xì)的分析了這道題筋帖，所以這次就簡(jiǎn)單的過一遍奸晴。

• dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]表示到第i天時(shí)買賣股票能獲得的最大利潤(rùn)，j==0表示當(dāng)天持有股票日麸，j==1當(dāng)天未持有股票寄啼。

• 狀態(tài)轉(zhuǎn)移方程，假設(shè)初始金額為0

  • 對(duì)于第i天代箭，

    • 如果持有股票墩划，說明在第i天或之前的某一天買入了股票。
      • 如果是在第i天買入了股票嗡综，至少第i-1天時(shí)是未持有股票的乙帮，根據(jù)dp數(shù)組的定義，第i-1天持有的金額是dp[i-1][1]极景，那么第i天時(shí)持有的金額為察净；
      • 如果在之前的某一天買入了股票，現(xiàn)在還應(yīng)該繼續(xù)持有股票盼樟，所以 氢卡，保持著持有之前買入的股票的狀態(tài)。
    • 如果不持有股票晨缴，說明在第i天或之前的某一天賣出了股票译秦。
      • 如果是在第i天買入了股票，至少第i-1天時(shí)是持有股票的击碗，根據(jù)dp數(shù)組的定義筑悴，第i-1天持有的金額是dp[i-1][0]，然后不要忘記賣出股票時(shí)要支付手續(xù)費(fèi)稍途，那么第i天時(shí)持有的金額為雷猪；
      • 如果在之前的某一天賣出了股票，第i天還不應(yīng)該買入股票晰房，所以求摇，保持之前的狀態(tài)即可

• 初始化dp數(shù)組射沟，第0天持有股票就是第0天買入股票，dp[0][0]=0-prices[i]与境；第0天未持有股票就是什么也不做验夯，dp[0][0]=0。dp數(shù)組其他的值初始化成不影響遞推公式計(jì)算結(jié)果的值即可摔刁，既然假設(shè)初始金額為0挥转，那初始化成0就可以。

• 遍歷順序共屈，就是今天的狀態(tài)依賴上一天的狀態(tài)绑谣，i從小到大遍歷

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<vector<int>> dp(prices.size(), {0, 0});
        dp[0][0] = 0 - prices[0];
        dp[0][1] = 0;

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

        return dp[prices.size() - 1][1];
    }
};

• 似乎股票問題相當(dāng)一部分能用貪心法解決，先寫完這一輪的動(dòng)態(tài)規(guī)劃再回頭看貪心法拗引。