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

前言

在前面的文章這種動態規劃你見過嗎——狀態機動態規劃之股票問題(上)我們已經介紹了兩個基本的股票問題，並且對狀態機動態規劃做出了簡要的介紹，以及在狀態機當中的狀態是如何進行轉換的，但是在前面的兩個問題當中狀態的個數比較少，可能不方便大家理解狀態機的含義，在本篇文章所談到的兩個問題當中狀態的數目還是比較多的，因此對於大家深入理解狀態機動態規劃可能會好一點。

賣股票的最佳時機 III

題目

給定一個陣列，它的第 i 個元素是一支給定的股票在第 i 天的價格。設計一個演演算法來計算你所能獲取的最大利潤。你最多可以完成兩筆交易。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

範例

範例1

輸入：prices = [3,3,5,0,0,3,1,4]

輸出：6

解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。隨後，在第 7 天（股票價格 = 1）的時候買入，在第 8 天（股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。

範例2

輸入：prices = [1,2,3,4,5]

輸出：4

解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。因為這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

這道題目跟之前的兩道題目不同之處在於，在上篇文章當中的兩道題要麼是能夠購買一次，要麼能夠購買無數次，而在本道題目當中只能夠購買兩次，在這種情況下我們應該如何定義各種狀態呢？

狀態表示陣列和狀態轉移

在這道題目當中我們也是二維陣列進行狀態的表示，二維陣列為dp[N][5]，5表示我們有5個狀態，dp[N][i]表示第N天的第i個狀態能夠多大的收益！（為了方便下面介紹，假設一天有一個股票，dp[N][]表示第N天的狀態，對應第N個股票的狀態）

dp[N][0]，表示第N天一次買入和賣出的操作都沒有過，那麼dp[N][0] = dp[N - 1][0]，跟前一天的狀態一樣，都沒有進行股票的買入和賣出，其實也可以直接令dp[N][0] = 0，因為沒有進行操作我們的收益肯定等於0。
dp[N][1]，表示第N天已經進行過第一次買入，這個買入可以是在第N天進行買入，也可以在前面N-1天買入，然後在第N天保持狀態。
- 如果第N天剛剛進行買入，那麼我們的收益就是從前一天一次買入和賣出都沒有操作轉移過來的，那麼就有dp[N][0] - prices[i]，因為根據上面的分析dp[N][0] = 0，那麼直接讓dp[N][1] = -prices[i]即可。
- 如果在前N-1天已經進行了買入，那麼在第N天就不行操作，即在第N天收入為0，即dp[N][1] = dp[N - 1][1]。
dp[N][2]，表示第N天已經進行過第一次賣出，這個狀態可以是在第N天進行賣出，也可以是在前面N-1天已經賣出，然後在第N天保持狀態
- 如果在第N天進行第一次賣出那麼我們在第N天的收益就等於prices[i]，再加上前N-1天買入一次的收益，即dp[N][2] = dp[N - 1][1] + prices[i]。
- 如果前N-1天已經賣出，那麼直接保持狀態即可，我們在第N天的收益就為0，那麼dp[N][2] = dp[N - 1][2]。
dp[N][3]，表示第N天已經進行過第二次買入，這個狀態可以是在第N天進行買入，也可以是在前面N-1天買入，然後在第N天保持狀態。
- 如果在第N天進行第二次買入那麼我們在第N天的收益就等於-prices[i]，再加上前N-1天買入賣出一次的收益，即dp[N][3] = dp[N - 1][2] - prices[i]。
- 如果前N-1天已經有了第二次買入的操作，那麼直接保持狀態即可，我們在第N天的收益就為0，那麼dp[N][3] = dp[N - 1][3]。
dp[N][4]，表示第N天已經進行過第二次賣出，這個狀態可以是在第N天進行買入，也可以是在前面N-1天賣出，然後在第N天保持狀態。
- 如果是在第N天賣出，那麼在第N天的收益為prices[i]，再加上前N-1天買入兩次賣出一次的收益dp[N][3]，那麼dp[N][4] = dp[N - 1][3] + prices[i]。
- 如果是前N-1天已經買入賣出兩次了，那麼直接保持前一天的狀態即可，即dp[N][4] = dp[N-1][4]。

根據上面的分析我們可以得到下面的狀態機（狀態轉移圖）：

相信看到這裡你就應該能夠理解為什麼這種動態規劃叫做狀態機動態規劃，因為在這種動態規劃當中資料存在很多狀態，而我們需要進行仔細的分析，分析清楚這裡面的狀態該如何進行轉移，進而分析出來各種狀態之間的轉移關係，這種模式跟狀態機非常像，因此叫做狀態機動態規劃。

資料流依賴分析和狀態轉移方程

假如可以買賣股票的天數一共有N天，那麼我們最終需要求出來的結果是dp[N][4]，表示第N天已經買入賣出2次，將兩次使用的機會都是用完了，為什麼我們最終的結果是dp[N][4]呢？這你可能疑惑萬一我買入一次賣出一次能夠得到的收益最大呢？我們是允許在同一天多次買入和賣出股票的，而在同一天買入和賣出股票收益為0，所以不影響最後的結果，因此買入賣出一次最終也可以轉移到買入賣出兩次（其中一次在同一天買入和賣出即可，我們在對陣列進行初始化的時候就需要進行多次買入和賣出（可以看下文當中對陣列初始化的分析）），因此我們最終需要返回的結果就是dp[N][4]。

而根據上面的分析我們知道，從上圖可以看出轉移到dp[N][4]這個狀態一共有兩種方式，我們應該選擇轉移之後兩者方式得到的價值比較大的那個，即dp[N][4] = max(dp[N - 1][4], dp[N - 1][3] + prices[i]);，而dp[N - 1][4]的轉移又有兩種方式我們也應該選擇其中較大的，dp[N - 1][3]也有兩種轉移方式，因此其也應該選擇兩者當中比較大的那個值，即dp[N][3] = max(dp[N - 1][3], dp[N - 1][2] - prices[N]);，同理我們可以得到其他狀態的轉移方程，每個資料都是需要選擇轉移之後價值最大的那個，最終我們的狀態轉移方程如下：

dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

動態規劃設計

在求解動態規劃問題的時候通常的步驟有以下幾個：

尋找能夠表示狀態的陣列dp，即我們需要尋找dp的含義，分析需要用幾緯陣列表示具體的狀態。
通過分析問題，尋找動態轉移公式。
初始化狀態陣列。
通過分析動態轉移方程，確定陣列的遍歷順序。

在前文當中我們已經完成了前兩步，現在需要對陣列進行初始化，第一天我們可以不買入一隻股票，那麼第一天我們的收益為0，即dp[0][0] = 0，我們也可以買入一隻股票，即dp[0][1] = -prices[0]，我們可以買入一隻再賣出，那等於不買，因為同一天價格都一樣，即dp[0][2] = 0，我們也可以二次買入，也就是先買入再賣出再買入，即dp[0][3] = -prices[0]，同樣的我們也可以進行兩次買入賣出，最終的收益也等於0，即dp[0][4] = 0。

綜合上面的分析，我們的初始化程式碼如下：

dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][3] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;

根據狀態轉移方程，我們知道第i天依賴於第i-1天的資料，因此我們遍歷的順序為從前到後進行遍歷。

程式碼

class Solution {
  public int maxProfit(int[] prices) {
    int[][] dp = new int[prices.length][5];
    // dp[i][0] 表示一次買入和賣出都沒有
    // dp[i][1] 表示第一次買入
    // dp[i][2] 表示第一次賣出
    // dp[i][3] 表示第二次買入
    // dp[i][4] 表示第二次賣出
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];
    for (int i = 1; i < prices.length; i++) {
      dp[i][0] = dp[i - 1][0];
      dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
      dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
      dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
      dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[prices.length - 1][4];
    // 注意資料之前傳遞依賴的關係
    // 因為要求 dp[N][4] 當中
    // 最大的值 因此需要求解 dp[N - 1][4] 和 dp[i - 1][3] 的最大值
    // ......
  }
}

上面的程式碼的時間和空間複雜度分別為\(O(n)\)和\(O(n)\)。

空間複雜度優化

其實我們可以使用一個單行陣列進行優化，優化程式碼如下：

class Solution {
  public int maxProfit(int[] prices) {
    int[] dp = new int[5];
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (int i = 1; i < prices.length; i++) {
      dp[0] = dp[0]; // 這一行可以不要的 放在這裡只是為了狀態轉移方程的完整
      dp[1] = Math.max(dp[1], dp[0] - prices[i]);
      dp[2] = Math.max(dp[2], dp[1] + prices[i]);
      dp[3] = Math.max(dp[3], dp[2] - prices[i]);
      dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4];
  }
}

我們現在來簡要分析一下上面的程式碼為什麼可行：

比如現在i=3，現在要進行更新，現在的dp陣列還是i=2的狀態，如果用二維陣列來表示的話，現在的單行陣列中的dp[i]相當於二維陣列當中的資料dp[2][i]，假如我們現在需要更新dp[3][2]，根據二維陣列的動態轉移方程，我們需要二維陣列第二行的資料dp[2][2]，但是此時的單行陣列當中的資料還沒有更新，也就是說dp[2]等於 dp[2][2]（前面的dp表示單行陣列，後面的dp表表示二維陣列的dp），因此還是上一個狀態的資料，因此更新沒有問題。

dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

根據上面的狀態轉移方程我們知道dp[3][2]依賴於dp[2][1]，而dp[2][1]相當於dp[1]，但是在下面的程式碼當中，我們在更新dp[2]之前dp[1]已經更新了，也就是說dp[1]已經是第三行的狀態了，即dp[1] = dp[3][1]，而現在更新的時候需要的是第二行的狀態，因此這就不對了。

class Solution {
  public int maxProfit(int[] prices) {
    int[] dp = new int[5];
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (int i = 1; i < prices.length; i++) {
      dp[0] = dp[0]; // 這一行可以不要的 放在這裡只是為了狀態轉移方程的完整
      dp[1] = Math.max(dp[1], dp[0] - prices[i]);
      dp[2] = Math.max(dp[2], dp[1] + prices[i]);
      dp[3] = Math.max(dp[3], dp[2] - prices[i]);
      dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4];
  }
}

那為什麼上面的程式碼又可行呢？

如果dp[1]是從上一行的dp[1]轉移而來，那麼就是符合我們的想法的，dp[2]使用的還是上一個(第2行)狀態的dp[1]，因為本行狀態的(第3行)dp[1]和第2行的dp[1]相等。
如果dp[1]是從dp[0] - prices[3]轉移過來的，那麼在這條語句dp[2] = Math.max(dp[2], dp[1] + prices[3]);當中，如果選擇的是dp[2]那麼也沒關係，因為他跟dp[1]沒有關係。如果選擇的是dp[1] + prices[3]，那麼也沒關係因為dp[1]減去了prices[3]，這一加一減相當於沒有收益，這並不影響最後的結果，因為這一賣一買都是在今天完成的，而對最終結果產生影響的肯定是在前面已經買入的操作（比如第2行的dp[1]就表示在之前進行第一次買入），而不會是在今天的買入，理解這一點就可以理解上的程式碼了。
其餘程式碼的影響也是類似的，都可以通過一加一減低消掉，最終都不影響最後的結果。

通過上述的優化之後空間複雜度變為\(O(1)\)。

賣股票的最佳時機 IV

題目

給定一個整數陣列 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。設計一個演演算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

範例

範例1

輸入：k = 2, prices = [2,4,1]

輸出：2

解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。

範例2

輸入：k = 2, prices = [3,2,6,5,0,3]

輸出：7

解釋：在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。隨後，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。

問題分析

這個問題和本文當中的第一個問題其實差不多，只不過上面的問題是最多完成兩筆交易，而在這個問題當中是最多可以完成k筆交易，這個問題相當於上面問題的推廣，我們再來分析一下上一道題目的動態轉移公式：

dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

上面的公式用一個公式表示就是：

\[dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] \pm prices[i]); \]

現在我們將這個問題進行推廣：

狀態表示
- dp[i][0] 表示一次買入和賣出都沒有。
- dp[i][2 * k - 1] 表示第 k 次買入。
  - 根據上文的分析，這個地方類似，有兩種狀態可以轉換成第k次買入這個狀態。
    - 如果前i-1天已經有k次買入了，則保持前面的狀態就行，即dp[i][2 * k - 1] = dp[i - 1][2 * k - 1]。
    - 如果前i-1天已經有k-1次買入和賣出了，那麼就需要進行買入，即dp[i][2 * k - 1] = dp[i - 1][2 * k - 2]- prices[i] 。
- dp[i][2 * k] 表示第 k 次賣出。
  - 同樣的，也有兩個狀態可以轉換成這個狀態。
    - 如果前i-1天已經有k次賣出了，則保持前面的狀態就行，即dp[i][2 * k] = dp[i - 1][2 * k]。
    - 如果前i-1天已經有k次買入，那麼就需要進行買入，即dp[i][2 * k] = dp[i - 1][2 * k - 1] + prices[i]。
根據上面的分析，那麼狀態轉移方程如下（其中j是偶數）：
```
dp[i][j - 1] = max(dp[i - 1][j - 1], dp[i - 1][j - 2] - prices[i]);
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
```
同理我們最終需要返回的結果就是dp[N][2 * k]。
陣列初始化
- 根據我們的分析，在買入之前必須賣出，因此在第一行當中所有的買入狀態的價值都是-pirces[0]，所有的賣出狀態的價值都是0，因為買入之後再賣出就相當於沒有買賣一樣。

程式碼

class Solution {
  public int maxProfit(int k, int[] prices) {
    if (prices == null || prices.length == 0)
      return 0;
    int m = 2 * k + 1;
    int[][] dp = new int[prices.length][m];
    // dp[i][0] 表示一次買入和賣出都沒有
    // dp[i][2 * k - 1] 表示第 k 次買入
    // dp[i][2 * k] 表示第 k 次賣出
    for (int i = 1; i < m; i += 2) {
      dp[0][i] = -prices[0];
    }
    for (int i = 1; i < prices.length; i++) {
      dp[i][0] = dp[i - 1][0];
      for (int j = 2; j < m; j += 2) {
        dp[i][j - 1] = Math.max(dp[i - 1][j - 1], dp[i - 1][j - 2] - prices[i]);
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);

      }
    }
    return dp[prices.length - 1][2 * k];
    // 注意資料之前傳遞依賴的關係
  }

}

總結

在本篇文章當中主要給大家介紹了另外兩種股票問題，在這兩個股票問題當中都有許多的狀態，狀態之間的轉化也比較複雜，在仔細分析上面兩個問題的狀態轉化之後相信你已經能夠理解狀態機動態規劃了，這種含有比較複雜的狀態之間的變化就叫做狀態機動態規劃，這種問題一般分析起來還是比較複雜的。

更多精彩內容合集可存取專案：https://github.com/Chang-LeHung/CSCore

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