這種動態規劃你見過嗎——狀態機動態規劃之股票問題(下)

2022 年 7 月 28 日
筆記
動態規劃, 算法

這種動態規劃你見過嗎——狀態機動態規劃之股票問題(下)

前言

在前面的兩篇文章這種動態規劃你見過嗎——狀態機動態規劃之股票問題(上)和這種動態規劃你見過嗎——狀態機動態規劃之股票問題(中)已經談了4道和股票問題相關的題目，詳細解釋了狀態機動態規劃和他的基本原理和應用方式。在本篇文章當中，會再介紹剩下的兩道股票問題，繼續深入和學習狀態機動態規劃。

最佳買賣股票時機含冷凍期

題目

給定一個整數數組prices，其中第 prices[i] 表示第 i 天的股票價格。

設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以儘可能地完成更多的交易（多次買賣一支股票）:賣出股票後，你無法在第二天買入股票 (即冷凍期為 1 天)。

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

示例

示例1:

輸入: prices = [1,2,3,0,2]
輸出: 3 
解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]

示例2:

輸入: prices = [1]
輸出: 0

狀態表示數組和狀態轉移方程

和前面的題目一樣首先還是需要進行狀態的定義和狀態轉移的分析，在這個問題當中我們用一個二維數組dp[i][j]表示各種不同的狀態下的收益，在這個問題當中我們有以下幾個狀態：

dp[i][0]，表示在遍歷到第i支股票的時候沒有進行一次買入和賣出。
- 在這個時候沒有進行買入和賣出，這個時候的收益和遍歷到第i-1支股票的時候沒有買入和賣出的情況是一樣的，他們的收益都等於0，即dp[i][0] = 0，dp[i - 1][0] = 0。
dp[i][1]，表示在遍歷到第i支股票的時候手中含有股票，這個情況可以由三種情況轉移過來：
- 在遍歷到第i-1支股票的時候手中已經存在股票了，這個時候只需要保持狀態，那麼在第i支股票的時候的收益和第i-1支股票的收益是相等的，即dp[i][1] = dp[i - 1][1]。
- 第二種情況就是在遍歷到第i-1支股票的時候手中不存在股票，那麼這個時候要想手中存在股票就需要進行買入了，那麼就需要花費prices[i]，那麼在遍歷到第i支股票的時候收益等於dp[i][1] = dp[i - 1][0] - prices[i]。
- 第三種情況是前一天是處於冷凍期（這裡所談到的冷凍期並不只是前2天賣出，導致的前一天的冷凍期，還有可能是更早之前賣出的，然後保持它的狀態，相當於是冷凍期的續期，只不過在續期當中是可以進行買股票的），那麼現在是可以進行買入的，即dp[i][1] = dp[i - 1][3] - prices[i]，其中dp[i][3]表示遍歷到第i支股票的時候處於冷凍期的收益。
- 綜合以上三種情況：
\[dp[i][1] = max(dp[i – 1][1], max(dp[i – 1][0] – prices[i], dp[i-1][3] – prices[i]))
\]
dp[i][2]，表示在第i支股票的時候手中不含有股票，可以轉移到這個狀態的狀態一共有兩種：
- 在遍歷到第i-1支股票的時候手中本來就不含有股票，那麼我們只需要保持狀態即可，即dp[i][2] = dp[i - 1][2]。
- 在遍歷到第i-1支股票的時候手中含有股票，那麼我們需要將這個股票進行售出，即dp[i][2] = dp[i - 1][1] + prices[i]。
- 綜合以上兩種情況：
\[dp[i][2] = max(dp[i – 1][2], dp[i – 1][1] + prices[i])
\]
dp[i][3]，表示在第i支股票的時候是處在冷凍期，這個狀態只能由一個狀態轉移過來，那就是前一天手中沒有股票（因為進行賣出了），即dp[i][3] = dp[i][2]。

數組的初始化和遍歷順序

根據上面的分析我們可以知道，在遍歷到第一支股票的時候如果持有股票的話就需要進行買入，那麼買入的狀態dp[0][1]的值就等於-prices[0]，賣出的狀態收益為0，冷凍期的狀態也等於0。根據狀態轉移方程第i行的數據依賴第i-1行，因此從前往後遍歷就行。

最大收益

根據上文當中我們設置的狀態，我們能夠獲取的最大的收益為dp[prices.length - 1][2], dp[prices.length - 1][3]兩者當中的一個，因為最終我們要想收益最大手中肯定沒有股票，而沒有股票的狀態有上述提到的兩個狀態。

\[max(dp[prices.length – 1][2], dp[prices.length – 1][3])
\]

代碼

class Solution {
  public int maxProfit(int[] prices) {
    // dp[i][0] 表示一次買入和賣出操作都沒有 這個值始終等於0，可以不用這個狀態
    // 但是為了完整將這個狀態留下來了
    // dp[i][1] 表示持有股票
    // dp[i][2] 表示不持有股票
    // dp[i][3] 賣出操作之後的冷凍期
    int[][] dp = new int[prices.length][4];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]),
          dp[i][0] - prices[i]); // 因為dp[i][0] 始終等於0 因此這裡可以直接寫 -prices[i] 也行
      dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
      dp[i][3] = dp[i - 1][2];
    }
    return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]);
  }
}

因為dp[i][0]始終等於0，所以將所有含dp[i][0]的地方都可以刪除，因此下面的代碼也是正確的。

class Solution {
  public int maxProfit(int[] prices) {
    // dp[i][0] 表示一次買入和賣出操作都沒有 這個值始終等於0，可以不用這個狀態
    // 但是為了完整將這個狀態留下來了
    // dp[i][1] 表示持有股票
    // dp[i][2] 表示不持有股票
    // dp[i][3] 賣出操作之後的冷凍期
    int[][] dp = new int[prices.length][4];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]),
          -prices[i]); 
      dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
      dp[i][3] = dp[i - 1][2];
    }
    return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]);
  }
}

數組優化——滾動數組

在上面的狀態轉移方程當中我們始終只使用了兩行的數據，因此我們可以只使用一個兩行的二維數組，然後進行交替使用（對i求2的餘數就可以了）就可以了，代碼如下：

class Solution {
  public int maxProfit(int[] prices) {
    int[][] dp = new int[2][4];
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      dp[i & 1][1] = Math.max(Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][3] - prices[i]),
          dp[i & 1][0] - prices[i]);
      dp[i & 1][2] = Math.max(dp[(i - 1) & 1][2], dp[(i - 1) & 1][1] + prices[i]);
      dp[i & 1][3] = dp[(i - 1) & 1][2];
    }
    return Math.max(dp[(prices.length - 1) & 1][2], dp[(prices.length - 1) & 1][3]);
  }
}

買賣股票的最佳時機含手續費

題目

給定一個整數數組 prices，其中 prices[i]表示第 i 天的股票價格；整數 fee 代表了交易股票的手續費用。

你可以無限次地完成交易，但是你每筆交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。

返回獲得利潤的最大值。

注意：這裡的一筆交易指買入持有並賣出股票的整個過程，每筆交易你只需要為支付一次手續費。

示例

示例1

輸入：prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出：8
解釋：能夠達到的最大利潤:  
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例2

輸入：prices = [1,3,7,5,10,3], fee = 3
輸出：6

狀態表示數組和狀態轉移方程

這道題其實和在這種動態規劃你見過嗎——狀態機動態規劃之股票問題(上)當中的第二道題很相似，唯一的區別就是這裡加上了手續費，其餘部分是一模一樣。

現在我們來分析一下如何進行狀態的轉移：

dp[i][0]的狀態如何從第i-1的狀態轉移過來：
- 如果第i-1個狀態是手中不存在股票，即dp[i-1][0]，那麼第i個狀態也沒有股票，那麼直接是dp[i][0] = dp[i - 1][0]，因為沒有進行交易。
- 如果第i-1個狀態手中存在股票，即dp[i-1][1]，那麼如果想在第i個狀態沒有股票，那麼就需要將股票賣出，那麼收益就為dp[i-1][1] + prices[i]，即dp[i][0] = dp[i-1][1] + prices[i]，但是在這個題目當中會有手續費，我們在賣出的時候需要繳納手續費，那麼我們的收益就變成dp[i][0] = dp[i-1][1] + prices[i] -fee。
- 綜合上面的兩種轉移方式可以得到下面的轉移方程：
\[dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i] -fee)
\]
dp[i][1]的狀態如何進行轉移：
- 如果第i-1個狀態是手中不存在股票，即dp[i-1][0]，那麼我們就需要從第i-1個手中不存在股票的狀態進行買入，那麼dp[i][0] = dp[i - 1][0] - prices[i]。
- 如果第i-1個狀態手中存在股票，即dp[i-1][1]，而第i個狀態有股票，因此不需要進行交易，即dp[i][1]=dp[i - 1][1]。
- 綜合上面的兩種轉移方式可以得到下面的轉移方程：
\[dp[i][1] = max(dp[i – 1][1], dp[i – 1][0] – prices[i]);
\]
綜合上面的兩個狀態：

\[\begin{cases}dp[i][0] = max(dp[i – 1][0], dp[i – 1][1] + prices[i] -fee)\\
dp[i][1] = max(dp[i – 1][1], dp[i – 1][0] – prices[i]);
\end{cases}
\]

代碼

class Solution {
  public int maxProfit(int[] prices, int fee) {
    int[][] dp = new int[prices.length][2];
    // dp[i][0] 表示不持有股票
    // dp[i][1] 表示持有股票
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
      dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[prices.length - 1][0];
  }
}

數組優化——滾動數組

class Solution {
  public int maxProfit(int[] prices, int fee) {
    int[][] dp = new int[2][2];
    // dp[i][0] 表示不持有股票
    // dp[i][1] 表示持有股票
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i] - fee);
      dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]);
    }
    return dp[(prices.length - 1) & 1][0];
  }
}

再優化

class Solution {
  public int maxProfit(int[] prices, int fee) {
    int[] dp = new int[2];
    // dp[0] 表示不持有股票
    // dp[1] 表示持有股票
    dp[1] = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
      dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
      dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    }
    return dp[0];
  }
}

上面的代碼優化和這種動態規劃你見過嗎——狀態機動態規劃之股票問題(中)當中的優化原理是一樣的。在下面的代碼當中，左邊的單行數組dp[0]和dp[1]相當於二維數組當中的dp[i][0]，dp[i][1]，右邊的單行數組dp[0]和dp[1]相當於二維數組的dp[i - 1][0]和dp[i - 1][1]。

dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee);
dp[1] = Math.max(dp[1], dp[0] - prices[i]);

但是我們會發現上面代碼的第二行會依賴dp[0]，這個dp[0]是第i-1行的狀態，但是dp[0]在第一行已經發生了更新，也就是說dp[0]已經更新到了第i行的狀態，那麼為什麼結果是對的呢？我們可以根據下面三條規則進行分析：

如果dp[0]取的是dp[0]，也就是說dp[0] > dp[1] + prices[i] - fee ，那麼dp[0]還是上一行的狀態，並不影響dp[1]的結果。
如果dp[0]取的是dp[1] + prices[i] - fee，但是dp[1]取的是上一行的dp[1]那麼對結果也沒有什麼影響。
如果dp[0]取的是dp[1] + prices[i] - fee而且dp[1]取的是dp[0] - prices[i]，那麼就有影響了，但是這一加一減其實沒有意義，還單純的需要繳納手續費，最終dp[0] - prices[i] = dp[1] + prices[i] - fee - prices[i] = dp[1] - fee < dp[1] ，因此這個狀態不會被最終的結果取到，被取到的狀態肯定都是第i-1行的dp[1]（因為dp[1]更大），也就是說這個狀態又會轉移到第二條當中，因此對最終的結果沒有影響。

總結

在本篇文章當中主要跟大家介紹了最後兩道股票問題，第一道題的狀態轉移還是比較複雜的，可能需要大家仔細進行體會，才能理解，尤其是關於冷凍期的狀態的轉換可能比較繞。本文當中的第二道題目跟之前的題目非常像，只需要在收益上減去手續費即可。相信看完這三篇文章，做完這六道題目你對狀態機動態規劃的基本原理已經很了解了，它和傳統的動態規劃最不一樣的就是有很多複雜的狀態之間的轉換，而且一般的動態規劃的題目都是多重循環，但是在狀態機動態規劃當中是單循環。

更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，了解更多計算機（Java、Python、計算機系統基礎、算法與數據結構）知識。

Tags: 動態規劃算法