狀態機動態規劃之股票問題總結

前言

在前面的三篇股票問題的文章當中我們一共介紹了6道關於股票相關的演演算法題，這些演演算法題的一個集中的特點就是狀態比較多，需要我們去仔細分析狀態之間的轉換，而這種狀態之間的轉換特變像狀態機，因此這種動態規劃也被稱作狀態機動態規劃。

如果需要仔細的去分析上面思維導圖當中的各個問題，可以參考下面的文章：

內容	連結
買賣股票的最佳時機I和II	這種動態規劃你見過嗎——狀態機動態規劃之股票問題(上)
買賣股票的最佳時機III和Iv	這種動態規劃你見過嗎——狀態機動態規劃之股票問題(中)
買賣股票的最佳時機含冷凍期和手續費	這種動態規劃你見過嗎——狀態機動態規劃之股票問題(下)

本篇文章就是對上面6個問題進行彙總方便大家查閱，如果大家想仔細分析這幾個問題還是上面三篇文章更合適，內容更加詳細，如果你想快速瞭解狀態機動態規劃，那麼這篇文章的狀態轉移分析應該能夠幫助你。

在本文談到的6個問題都是動態規劃的問題，因此你可以需要熟悉一下動態規劃的套路，在求解動態規劃問題的時候通常的步驟有以下幾個：

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

買賣股票的最佳時機I

給定一個陣列 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。你只能選擇某一天買入這隻股票，並選擇在未來的某一個不同的日子賣出該股票。設計一個演演算法來計算你所能獲取的最大利潤。返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

狀態表示陣列

在這個問題當中我們用一個二維陣列去表示我們的狀態，在這個問題當中主要有兩個狀態，一個是手上有股票，另一是手上沒有股票：

dp[i][0]表示在第i天手上沒有股票能夠獲得的最大的收益，比如我們在第一天的沒有股票的收益為0元。
dp[i][1]表示在第i天手上存在股票能夠獲得的最大的收益，比如我們在第一天買入股票之後收益為-prices[0]。

那麼我們最後的答案是dp[N][0]，這個表示在最後一天，我們的手中不存在股票，即我們將股票賣出去能夠獲取的最大的收益。

狀態轉移方程

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

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] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) \]
dp[i][1]的狀態如何進行轉移：
- 如果第i-1個狀態是手中不存在股票，即dp[i-1][0]，而第i個狀態有股票，那麼dp[i][0] = -prices[i]，因為買入股票，而且只能夠買入一次，因此直接等於-prices[i]即可，注意這裡不能是dp[i - 1][0] - prices[i]，因為在dp[i-][0]當中可能存在先買入再賣出的情況，而題幹要求只能買入賣出一次。
- 如果第i-1個狀態手中存在股票，即dp[i-1][1]，而第i個狀態有股票，因此不需要進行交易，即dp[i][1]=dp[i - 1][1]。
- 綜合上面的兩種轉移方式可以得到下面的轉移方程：
\[dp[i][1] = max(dp[i - 1][1], -prices[i]); \]

參考程式碼如下：

class Solution {
  public int maxProfit(int[] prices) {
    int[][] dp = new int[prices.length][2];
    // 初始化陣列 dp[0][0] 預設等於0 不用
    // 顯示初始化
    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]);
      dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    }
    return dp[prices.length - 1][0];
  }
}

進行陣列空間優化

class Solution {
  public int maxProfit(int[] prices) {
    int[][] dp = new int[2][2];
    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]);
      dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], -prices[i]);
    }
    return dp[(prices.length - 1) & 1][0];
  }
}

買賣股票的最佳時機 II

給你一個整數陣列 prices ，其中 prices[i] 表示某支股票第 i 天的價格。在每一天，你可以決定是否購買和/或出售股票。你在任何時候最多只能持有一股股票。你也可以先購買，然後在同一天出售。返回你能獲得的最大利潤。

狀態表示陣列

在這個問題當中我們用一個二維陣列去表示我們的狀態，在這個問題當中主要有兩個狀態，一個是手上有股票，另一是手上沒有股票：

dp[i][0]表示在第i天手上沒有股票能夠獲得的最大的收益，比如我們在第一天的沒有股票的收益為0元。
dp[i][1]表示在第i天手上存在股票能夠獲得的最大的收益，比如我們在第一天買入股票之後收益為-prices[0]。

那麼我們最後的答案是dp[N][0]，這個表示在最後一天，我們的手中不存在股票，即我們將股票賣出去能夠獲取的最大的收益。

狀態轉移方程

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

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] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) \]
dp[i][1]的狀態如何進行轉移：
- 如果第i-1個狀態是手中不存在股票，即dp[i-1][0]，而第i個狀態有股票，這道題目和上一道題目只有這個地方是不一致的，在上一道題當中dp[i][0] = -prices[i]，這是因為只能夠買入股票一次，具體原因是在dp[i - 1][0]當中可以存在股票買入，而且已經賣出這種情況，而第一題只能買入賣出一次，而在這道題目當中，能夠買賣股票多次，因此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])\\ dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); \end{cases} \]

參考程式碼如下：

class Solution {
  public int maxProfit(int[] prices) {
    int[][] dp = new int[2][2];
    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]);
      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];
  }
}

買賣股票的最佳時機 III

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

狀態表示陣列

在這道題目當中我們也是二維陣列進行狀態的表示，二維陣列為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]);

程式碼如下：

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] 的最大值
    // ......
  }
}

買賣股票的最佳時機 IV

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

狀態表示陣列和動態轉移方程

這個問題上面一個問題其實差不多，只不過上面的問題是最多完成兩筆交易，而在這個問題當中是最多可以完成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];
    // 注意資料之前傳遞依賴的關係
  }
}

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

給定一個整數陣列prices，其中第 prices[i] 表示第 i 天的股票價格。設計一個演演算法計算出最大利潤。在滿足以下約束條件下，你可以儘可能地完成更多的交易（多次買賣一支股票）:賣出股票後，你無法在第二天買入股票 (即冷凍期為 1 天)。

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

狀態表示陣列和狀態轉移方程

和前面的題目一樣首先還是需要進行狀態的定義和狀態轉移的分析，在這個問題當中我們用一個二維陣列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]);
  }
}

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

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

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

返回獲得利潤的最大值。

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

狀態表示陣列和狀態轉移方程

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

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

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];
  }
}

總結

綜合上面6道題目可以發現像這種題目最困難的地方是尋找對狀態的定義和狀態轉移的分析，一旦能夠分析出來這一步，那麼後續的操作就變得比較簡單了，我們只需要按部就班的根據我們定義的狀態和狀態轉移方程用程式碼進行實現即可，在寫出程式碼之後我們還可以分析資料之間的依賴關係，通過這種依賴關係或許我們還可以進行空間的優化，這個問題就得具體問題具體分析了！！！

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

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