這種動態規劃你見過嗎——狀態機動態規劃(上)

前言

在本篇文章當中主要通過介紹各種股票問題跟大家介紹狀態機動態規劃，主要了解在股票問題當中是如何在動態規劃當中進行狀態轉移的，通過仔細剖析狀態轉移過程給大家介紹狀態機動態規劃。所謂狀態機，就是有很多狀態和他們之間的轉移關係組成起來形成系統，這個說法看起來有點高大上，其實很簡單，在後面講動態規劃解法的時候大家就明白了。

買賣股票的最佳時機I

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

範例 1：

輸入：[7,1,5,3,6,4]

輸出：5

解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大於買入價格；同時，你不能在買入前賣出股票。

範例 2：

輸入：prices = [7,6,4,3,1]

輸出：0

解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。

暴力解法

在這個問題當中，我們的任務是在某一天買入股票，然後在未來某天再將股票賣出去，那麼我們就可以用一個二重回圈，第一層迴圈遍歷每一天的股票，第二層迴圈遍歷該天之後的股票，然後找到差值最大的那一天即可，也就是尋找某天后麵價值最高的股票！通過做差得到差值，將差值最大的返回即可！

class Solution {
  public int maxProfit(int[] prices){
    int ans = 0;
    for (int i = 0; i < prices.length - 1; i++) {
      for (int j = i + 1; j < prices.length; j++) {
        ans = Math.max(ans, prices[j] - prices[i]);
      }
    }
    return ans;
  }

}

上面的程式碼的時間複雜度為\(O(n^2)\)，空間複雜度為\(O(1)\)，由於時間複雜度過高，上面的程式碼在Leetcode上面提交會超時。

貪心解法

在暴力解法當中我們思考的是尋找某天后面的最大值，在這個問題當中我們可以換一個角度，就是尋找某天前面股票價值最低的那一天，然後在那一天買進，在當天賣出即可，這個效果和上面暴力解法是一樣的。這樣的話我們可以用一個陣列mins去存某一天前面價值最小的股票，然後做一個減法即可，即prices[i] - mins[i]，這樣我們就得到了在第i個位置賣出能夠得到的最大的價值，那麼我們再比較所有的這些值，我們就可以找到最後的答案了！這樣的話我們可以將時間複雜度降低到\(O(n)\)。

class Solution {
  public int maxProfit(int[] prices) {
    int ans = 0;
    int[] mins = new int[prices.length];
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < prices.length; i++) {
      min = Math.min(min, prices[i]);
      mins[i] = min;
    }
    for (int i = 0; i < prices.length; i++) {
      ans = Math.max(ans, prices[i] - mins[i]);
    }
    return ans;
  }
}

上面的程式碼的時間複雜度為\(O(n)\)，空間複雜度也是\(O(n)\)，其實仔細思考一下我們還可以降低空間複雜度：

class Solution {
  public int maxProfit(int[] prices) {
    int low = Integer.MAX_VALUE;
    int ans = 0;
    for (int i = 0; i < prices.length; i++) {
      low = Math.min(prices[i], low);
      ans = Math.max(ans, prices[i] - low);
    }
    return ans;
  }
}

我們在第一次遍歷的時候可以用一個值low儲存第i個位置左邊最小的值即可，並且在遍歷的過程當中不斷更新low值，而且我們在遍歷的時候可以順便求出對應位置的能夠獲取的最大價值，可以避免第二次遍歷。在這個情況下我們的時間複雜度為\(O(n)\)，空間複雜度為\(O(1)\)。

動態規劃解法

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

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

狀態表示陣列

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

• 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]); \]

  整個狀態轉移過程如下圖所示：
  

上面所談到的有兩種狀態，一種是有股票，一種是沒有股票，這兩種狀態需要從第i-1行轉移到第i行，即從第i-1行的有股票和無股票狀態轉移到第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];
  }
}

陣列優化（捲動陣列優化）

我們可以仔細分析一下上面的狀態轉移方程，可以發現第i行，只依賴第i-1行，因此我們只使用兩行陣列即可，第一行推測出第二行，第二行推測出來的結果再存回第一行.......

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 % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);
      dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], -prices[i]);
    }
    return dp[(prices.length - 1) % 2][0];
  }
}

可以使用位運算稍微優化一下（下面程式碼優化的依賴原理：\(a \& (2^n - 1) = a \% 2^n\)）：

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

最終經過上面的優化動態規劃的時間和空間複雜度可以優化到\(O(n)\)和\(O(1)\)。

小結

在上文當中主要介紹了買賣股票的最佳時機I各種解決辦法，其中最主要想介紹的就是動態規劃的方法了，而在動態規劃當中最重要的就是狀態之間如何進行轉換，這個題中其實很像狀態機中的狀態轉換，在這個問題當中只有兩種狀態之間的轉換——有股票和沒股票，大家如果要弄明白狀態機動態規劃演演算法，那就需要深刻的去理解上面狀態轉換的過程。

買賣股票的最佳時機 II

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

範例1:

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

輸出：7

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

範例 2：

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

輸出：4

解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。
總利潤為 4 。

這道題和第一題的區別就是，在這道題當中你可以買賣股票多次，但是最多隻能持有一隻股票，因此這道題和第一題的大多數情況是相同的。

狀態表示陣列

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

• 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]); \]

• 綜合上面的兩個狀態：

參考程式碼如下：

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

貪心解法

因為我們可以無數次買入賣出，因此只要存在前一天的價格低於今天的價格，那麼我們就可以在前一天買入，在今天賣出，在這種情況下我們的收益就是最大的，因為我們抓住了「每一次賺錢的機會」。

• 比如prices=[1, 2, 3]，我們的收益就等於(2 - 1) + (3 - 2) = 2，這個過程相當於在第一天買入，第二天賣出，第二天再買入（注意題目當中說明了一天可以同時買入和賣出，只需要保證手上的股票不超過兩個），第三天賣出。
• 又比如prices=[4, 5, 3, 6]，我們的收益等於(5 - 4) + 0 + (6 - 3) = 4，這個過程相當於第一天買入第二天賣出，第三天再買入第四天賣出。

程式碼如下：

class Solution {
  public int maxProfit(int[] prices) {
    int ans = 0;
    int n = prices.length;
    for (int i = 1; i < n; ++i) {
      ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
  }
}

總結

在本篇文章當中主要給大家介紹了兩個股票問題，這兩個問題比較中規中矩的方法就是使用動態規劃，但是也可以使用貪婪法巧妙求解。在本文當中最想跟大家介紹的還是狀態之間的轉換，但是在本文當中的兩個問題當中涉及的狀態還是比較少，只有含有股票和不含有股票兩種狀態，但是也可以看作狀態機當中狀態之間的轉換。下篇當中的題目狀態會稍微多一點，可能大家理解起來更加容易一點！

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

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