LeetCode上的各種股票最大收益

dp數組含義：

本題在某一天共可能有兩種狀態：

• 持有股票
• 不持有股票

我們構造的 dp 數組的規模為 $2\times n$，在 C++ 中，即為：vector<<vevtor<int>> dp(prices.size(), vector<int> (2, 0));

• $dp[i][0]$ 表示在第 $i$ 天結束后，在持有股票的狀態下的最大收益
• $dp[i][1]$ 表示在第 $i$ 天結束后，在不持有股票的狀態下的最大收益

遞推公式：

• 對于第 $i$ 天持有股票時的收益，即 $dp[i][0]$，可能由以下情況推導而來：

  • 第 $i?1$ 天是也是持有股票的，即當日未進行任何操作：$dp[i?1][0]$

  • 第 $i?1$ 天是未持有股票的，即當日購買了股票，由于我們只能進行一次股票買賣操作，因此在購買股票之前的 $dp[i?1][1]$ 一定是 0，因此應當減去當日股票價格：$0?prices[i]$

  應當取最大值，從而 $dp[i][0]=max(dp[i?1][0],?prices[i])$

• 對于第 $i$ 天未持有股票時的收益，即 $dp[i][1]$，可能由以下情況推導而來：

  • 第 $i?1$ 天是是持有股票的，即當日將股票賣出，應當 $dp[i?1][0]$ 加上當日股票價格：$dp[i?1][0]+prices[i]$
  • 第 $i?1$ 天是未持有股票的，即當日無操作：$prices[i?1][1]$

  應當取最大值，從而 $dp[i][1]=max(dp[i?1][1],dp[i?1][0]+prices[i])$

初始化：

dp 數組中所有項需在 $dp[0][0]$、$dp[0][1]$ 確定的情況下得到。

• $dp[0][0]$ 表示第一天持有股票，即第一天購入，應為 $?prices[0]$
• $dp[0][1]$ 表示第一天未持有股票，應為 0

遍歷順序：

從前向后

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int lens = prices.size();vector<vector<int>> dp(lens, vector<int> (2));dp[0][0] = -prices[0], dp[0][1] = 0;for (int i=1; i<lens; ++i) {dp[i][0] = max(dp[i-1][0], -prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);}return dp[lens-1][1];}
};

空間優化：

很明顯，第 $i$ 天的情況只依賴于前一天的情況，而與再前面的情況沒有關系，因此，我們沒有必要維護一整個 dp 數組，而是維護常數變量即可，優化后：

class Solution {
public:int maxProfit(vector<int>& prices) {int lens = prices.size();vector<vector<int>> dp(2, vector<int> (2));dp[0][0] = -prices[0], dp[0][1] = 0;for (int i=1; i<lens; ++i) {dp[1][0] = max(dp[0][0], -prices[i]);dp[1][1] = max(dp[0][1], dp[0][0] + prices[i]);dp[0] = dp[1];}return dp[1][1];}
};

另一種做法：

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0, prevMin = INT_MAX;for (int n: prices) {ans = max(ans, n - prevMin);prevMin = min(prevMin, n);}return ans;}
};

本題與121 題的唯一區別在于可以多次買賣股票，但要注意同時只能持有一只股票

dp數組含義：

• $dp[i][0]$ 表示在第 $i$ 天結束后，持有股票時的最大收益
• $dp[i][1]$ 表示在第 $i$ 天結束后，不持有股票時的最大收益

遞推公式：

注意由于這里與上一題的唯一區別在于允許多次股票買賣，因此遞推公式與上面的四種情況基本相同，唯一一點在于由于我們可以進行多次買賣，所以在某次購買股票之前的未持有股票的收益不一定是 0 了（我們可能在這次操作之前已經通過幾次操作收獲了一些利潤）。

即對于 $dp[i][0]$ 在前一日不持有股票的情況從 $0?prices[i]$ 變為了 $dp[i?1][1]?prices[i]$，從而 $dp[i][0]=max(dp[i?1][0],dp[i?1][1]?prices[i])$

初始化、遍歷順序與前題類似。

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int lens = prices.size();vector<vector<int>> dp(lens, vector<int> (2));dp[0][0] = -prices[0], dp[0][1] = 0;for (int i=1; i<lens; ++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]);}return dp[lens-1][1];}
};

注意代碼中的唯一區別在于：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);

原因上面已經解釋過。

空間優化的實現與上面也類似，這里就不貼了。

另一種寫法：

本題有另一種做法，由于我們可以進行無限次交易且當日即可以買入又可以賣出，所以考慮：

[7, 1, 5, 6] 第二天買入，第四天賣出，收益最大（6-1），所以一般人可能會想，怎么判斷不是第三天就賣出了呢? 這里就把問題復雜化了，根據題目的意思，當天賣出以后，當天還可以買入，所以其實可以第三天賣出，第三天買入，第四天又賣出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接簡化為只要今天比昨天大，就賣出。

class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0;for (int i=1; i<prices.size(); ++i) {int profit = prices[i] - prices[i-1];ans = max(ans, ans + profit);}return ans;}
};

本題相較于前面兩題要復雜不少，關鍵是最多兩次交易，即有可能可以是 0，1，2 次交易，我們需要列舉處理的情況多了不少。

dp數組的定義：

本題中，我們一共要考慮每一天的五種狀態：

• 尚未進行操作
• 第一次買入后
• 第一次賣出后
• 第二次買入后
• 第二次賣出后

注意我們這里要強調各個狀態是 買入/賣出 后 ，即不一定是當日買入/賣出，可能是 $i?1$，$i?2$ …日進行的操作，都歸為該狀態。并且，注意到，這些狀態是有序的，即一定是一次經歷到的。

由此，我們 dp 數組的含義為：$dp[i][j]$ 表示，第 $i$ 天處于狀態 $j$ 時的最大收益。

遞推公式：

• 對于第 $i$ 日結束后。處于第一次買入后狀態，即 $dp[i][1]$，可能由以下情況推導而來：

  • 前面已經買入，當日未進行操作：$dp[i?1][1]$
  • 當日買入：$dp[i?1][0]?prices[i]$

  取最大值，則有：$dp[i][1]=max(dp[i?1][1],dp[i?1][0]?prices[i])$

• 對于第 $i$ 日處于第一次賣出后，即 $dp[i][2]$，可能由以下情況推導而來：

  • 前面已經賣出，當日未進行任何操作：$dp[i?1][2]$
  • 當日賣出：$dp[i?1][1]+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(vector<int>& prices) {int lens = prices.size();vector<vector<int>> dp(lens, vector<int> (5));dp[0][1] = -prices[0], dp[0][3] = -prices[0];for (int i=1; i<lens; ++i) {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]);}return dp[lens - 1][4];}
};

優化代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int fstBuy = INT_MIN, fstSell = 0;int secBuy = INT_MIN, secSell = 0;for (int p: prices) {fstBuy = max(fstBuy, -p);fstSell = max(fstSell, fstBuy + p);secBuy = max(secBuy, fstSell - p);secSell = max(secSell, secBuy + p);}return secSell;}
};

上一題的一般化，分好奇偶即可：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.empty()) return 0;int lens = prices.size();int wide = 2 * k + 1;vector<vector<int>> dp(lens, vector<int> (wide, 0));for (int j=0; j<wide; ++j) if (j % 2 == 1) dp[0][j] = -prices[0];for (int i=1; i<lens; ++i) {dp[i][0] = dp[i-1][0];for (int j=1; j<wide; ++j) {if (j % 2 == 1) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i]);else if (j % 2 == 0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i]);}}return dp[lens - 1][wide - 1];}
};

dp數組含義：

本題中每天可能的狀態有三種：

• 持有股票
• 不持有股票，今天賣出，后一天為冷凍期
• 不持有股票，非今天賣出，后一天不為冷凍期

$dp[i][j]$ 表示第 $i$ 天結束后，在第 $j$ 中狀態下的最大收益

遞推公式：

• 當日結束后為持有股票狀態時，即 $dp[i][0]$ ，可能由以下情況推導而來：

  • 當日買入股票，今天不能是冷凍期， $dp[i?1][2]?prices[i]$
  • 之前就已經買入了股票，當日未進行操作：$dp[i?1][0]$

  則，$dp[i][0]=max(dp[i?1][0],dp[i?1][2]?prices[i])$

• 當日賣出，即 $dp[i][1]$

  • 今天賣出，前一天必為持股狀態，$dp[i?1][0]+prices[i]$

  則，$dp[i][1]=dp[i?1][0]+prices[i]$

• 非當日賣出，即 $dp[i][2]$，可能由以下情況推導而來：

  • 前一日賣出，今日冷凍期，$dp[i?1][1]$
  • 非前一日賣出，今日非冷凍期：$dp[i?1][2]$

  則 $dp[i][2]=max(dp[i?1][1],dp[i?1][2])$

初始化：除了第一天就買股票 $dp[0][0]=?prices[0]$ 外全 0。

遍歷順序：從前到后即可。

代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int lens = prices.size();vector<vector<int>> dp(lens, vector<int> (3, 0));dp[0][0] = -prices[0];for (int i=1; i<lens; ++i) {dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);dp[i][1] = dp[i-1][0] + prices[i];dp[i][2] = max(dp[i-1][2], dp[i-1][1]);}return max(dp[lens - 1][1], dp[lens - 1][2]);}
};

就加個手續費，和 122 區別不大。

dp數組含義：

本題中每一天結束后有兩種狀態：持有股票和不持有股票

• $dp[i][0]$ 表示第 $i$ 天結束后處于持股狀態時的最大收益
• $dp[i][1]$ 表示第 $i$ 天結束后處于未持股狀態時的最大收益

遞推公式：

• 對于第 $i$ 天結束后，處于持股狀態，即 $dp[i][0]$，可能由兩種狀態推導得到：

  • 前面買入，當日未進行操作：$dp[i?1][0]$
  • 當日買入，并支付手續費 $dp[i?1][1]?prices[i]?fee$

  則：$dp[i][0]=max(dp[i?1][0],dp[i?1][1]?prices[i]?fee)$

• 對于第 $i$ 天結束后，處于未持股狀態，即 $dp[i][1]$，可能由兩種狀態推導得到：

  • 一直未買入或前面已賣出，當日未進行操作：$dp[i?1][1]$
  • 當日賣：$dp[i?1][0]+prices[i]$

  則：$dp[i][1]=max(dp[i?1][1],dp[i?1][0]+prices[i])$

代碼：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int lens = prices.size();vector<vector<int>> dp(lens, vector<int> (2));dp[0][0] = -prices[0] - fee;for (int i=1; i<lens; ++i) {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]);}return dp[lens - 1][1];}
};