买股票的最佳时机（六种题解dp）
引言
買股票的最佳時機(jī)類的題目也是很經(jīng)典的動態(tài)規(guī)劃題目，出題人通過各種花里胡哨的買股票方法來考察（虐待）你，下面我們就開始看看一類的題目的各種花樣；
買股票的最佳時機(jī)
給定一個數(shù)組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設(shè)計一個算法來計算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 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。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
這道題意思就是在某一天買入股票，另一天賣出，使利潤最大；
1，dp[i][0]表示第 i 天不持有股票的最大利潤
dp[i][1]表示第 i 天持有股票最大利潤
2，因為只會買和賣一次，所以肯定會現(xiàn)有買入再有賣出，則
2.1，第i-1天就持有股票，那么就保持現(xiàn)狀，為dp[i - 1][1]
如果沒有股票就是第 i 天買入的，為- prices[i]，則有
2.2，第i-1天就不持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 dp[i - 1][0]
如果持有股票那么就是第 i 天賣出的，為dp[i - 1][1] + prices[i]，則有
3，如果第0天不持有股票，則dp[0][0] = 0;
如果第0天持有股票，則dp[0][1] = -prices[0];
4，由轉(zhuǎn)移方程可以看出dp[i]都是有dp[i - 1]推導(dǎo)出來的，那么一定是從前向后遍歷。
代碼如下
這道題沒有什么太多技巧，只需要了解到如何巧妙地使用數(shù)組表示持有股票和不持有股票即可；
買賣股票的最佳時機(jī) II
給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
這道題和一道題唯一區(qū)別就是：
第一道題的股票只會買賣一次
這道題會買賣多次；
很簡單，只需要在買股票的地方改動一下就可以了
因為會多次買入股票，所以買入股票的時候，可能會有之前買賣的利潤dp[i - 1][0]，所以dp[i - 1][0] - prices[i]
其余的地方?jīng)]有什么不一樣的，代碼如下：
這道題也不是多難，只是多了點小變換，我們來看下一道題；
買股票的最佳時機(jī)III
給定一個數(shù)組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 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 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這個情況下, 沒有交易完成, 所以最大利潤為0。
示例 4：
輸入：prices = [1]
輸出：0
提示：
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5
這個和前兩個又不一樣了，這個只讓完成兩次交易，而且是最多，這意味著你可以買賣一次或者兩次或者不買賣，該怎么做？
1，這里的dp數(shù)組可以重新設(shè)計一下：
1是第一次買入
2是第一次賣出
3是第二次買入
4是第二次賣出
dp[i][j]中 i表示第i天，j為 [0 - 4] 五個狀態(tài)，dp[i][j]表示第i天狀態(tài)j所剩最大現(xiàn)金
這樣看起來就很簡單了吧，我們可以列出轉(zhuǎn)移方程
2，
3，初始化也很簡單，就四種情況
dp[0][1] = dp[0][3] = -prices[0]
dp[0][2] = dp[0][4] = 0;
4,循環(huán)順序還是一樣，從前向后；
代碼如下：
這個代碼有個優(yōu)化版本很好看出來，就直接上代碼了
class Solution { public:int maxProfit(vector<int>& prices) {int n = prices.size();int buy1 = -prices[0], sale1 = 0;int buy2 = -prices[0], sale2 = 0;for (int i = 1; i < n; ++i) {buy1 = max(buy1, -prices[i]);sale1 = max(sale1, buy1 + prices[i]);buy2 = max(buy2, sale1 - prices[i]);sale2 =max(sale2, buy2 + prices[i]);}return sale2;} };這就是用了四個變量代替了dp1，2，3，4四種情況；
這道題就有點難度了，和前兩道題思路有一點不同，但是整體思路還是一樣的；
再來一道試試；
買股票的最佳時期IV
給定一個整數(shù)數(shù)組 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 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 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
這道題交易次數(shù)變成了隨機(jī)次數(shù)k次，該怎么做？
1，可以分別設(shè)一個vector容器buy[j]和sale[j]，分別表示 j 次的買入和賣出的最大價格；
2，如果第 j 次買入的最大利潤，則有
buy[j] = max(buy[j], sale[j - 1] - prices[i]);
第j次賣出的最大利潤為：
sale[j] = max(sale[j], buy[j] + prices[i]);
很好理解，就不解析了；
3，因為buy要求最大值，所以開始就初始化為INT_MIN；
而由轉(zhuǎn)移方程又可以看出來，sale需要初始化為0；
4，這里的遍歷需要在價格里面多加一個交易的循環(huán)，且都是從前往后的循環(huán)；
代碼如下：
class Solution { public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<int> buy(k + 1, INT_MIN), sale(k + 1, 0);for (int i = 0; i < n; ++i) {for (int j = 1; j <= k; ++j) {buy[j] = max(buy[j], sale[j - 1] - prices[i]);sale[j] = max(sale[j], buy[j] + prices[i]); }}return sale[k];} };這道題同樣有些難度，但是還沒完，下面還有一道，
買股票的最佳時機(jī)含冷凍期
給定一個整數(shù)數(shù)組，其中第 i 個元素代表了第 i 天的股票價格 。?
設(shè)計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
直接分析了：
1，分為三種情況
dp[i][0]: 第i天手上持有股票的最大收益
dp[i][1]: 手上不持有股票，并且處于冷凍期中第i天的累計最大收益
dp[i][2]: 手上不持有股票，并且不在冷凍期中第i天的累計最大收益
2，三種情況的轉(zhuǎn)移方程：
dp[i][0]: 因為此時持有股票，只會有兩種情況，第一種是前一天就持有dp[i - 1][0]，第二種是今天剛買，要想賣入股票需要不處在冷凍期，所以為dp[i - 1][2] - prices[i]
dp[i][1]: 此時沒有持有股票，且處在冷凍期，所以只會有一種情況，就是前一天持有股票然后賣掉了，即為dp[i - 1][0] + prices[i]
dp[i][2]: 這時沒有持有股票，但是不在冷凍期，那么就有兩種情況，第一種是前一天就沒有持有股票且不處在冷凍期，
為 dp[i - 1][2]，第二種是前一天處在冷凍期，dp[i - 1][1]；
由此可得轉(zhuǎn)移方程為：
3，持有股票，初始化dp[0][0] = -prices[0]，買入股票所省現(xiàn)金為負(fù)數(shù)。
其余不持有股票的情況初始化為0；
4，遍歷順序依舊是從前到后，遍歷每天股票價格；
代碼如下：
對于股票類問題還有最后一道，但是不是多難了；
買賣股票的最佳時機(jī)含手續(xù)費
給定一個整數(shù)數(shù)組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負(fù)整數(shù) fee 代表了交易股票的手續(xù)費用。
你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。返回獲得利潤的最大值。
注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費。
示例 1: 輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2 輸出: 8
解釋: 能夠達(dá)到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee <50000.
這道題無非就多了手續(xù)費，其余的和買股票的最佳時機(jī)II可以說一模一樣，
唯一注意的地方就是在賣出股票的時候把手續(xù)費fee付了就可以了；
直接上代碼了
總結(jié)
這就是所有股票問題了，有許多相似的地方，不論怎么變化只要會靈活使用變換就可以了；
總結(jié)
以上是生活随笔為你收集整理的买股票的最佳时机（六种题解dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 打家劫舍系列（dp）
- 下一篇： 最长递增子序列 最长连续递增序列