這一期是和上一期是連著的，包含的題目如下：
這三個題目所需要的思路是很相近的，先給出第一個的題目。
給定一個數(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
第一步——理解題意
就是給你一個數(shù)組，交易最多兩次，獲得最大金額。
第二步——思考遞歸狀態(tà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。
我們可以把這個分為五部分——|3,3,5|0,0|3|1|4|
- 沒有操作 （其實(shí)我們也可以不設(shè)置這個狀態(tài)）——3,3,5
- 第一次持有股票——0,0
- 第一次不持有股票——3（此時正好賣出）
- 第二次持有股票——1
- 第二次不持有股票——4（此時正好賣出）
它們對應(yīng)的遞歸公式是這樣的：
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]);第三步——進(jìn)行初始化
dp[0][0]=0;(因為這個時候還什么都沒干）
dp[0][1]=-prices[0];(因為這個時候買入第一次）
dp[0][2]=0;(先初始化為0，避免影響后面的賺的金額）
dp[0][3]=-prices[0];(也把它初始化為prices[0]，是因為有可能整個數(shù)組只需要一次交易，不需要第二次交易）
dp[0][4]=0;(同理，先初始化為0，避免影響后面的賺的金額）
給出代碼:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0) return 0;
vector<vector<int>>dp(len,vector<int>(5,0));
dp[0][1]=-prices[0];
dp[0][3]=-prices[0];
for(int i=1;i<len;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[len-1][4];
}
};這個題目就到此結(jié)束了，但接下來還有兩個跟他很相似的題目：
買賣股票的最佳時機(jī)IV
它和題1的不同就是把這個次數(shù)給抽象化了——你最多可以完成 k 筆交易
狀態(tài)表示為：文章來源：http://www.zghlxwxcb.cn/news/detail-803718.html
- 0 表示不操作
- 1 第一次買入
- 2 第一次賣出
- 3 第二次買入
- 4 第二次賣出
- .....
除了0以外，偶數(shù)就是賣出，奇數(shù)就是買入。
題目要求是至多有K筆交易，那么j的范圍就定義為 2 * k + 1 就可以了。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1;i < prices.size(); i++) {
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];
}
};最佳買賣股票時機(jī)含冷凍期
- 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
- 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
注意這里是可以盡可能完成更多的交易，所以它這里是和買賣股票的最佳時機(jī)II相似，就是多了一個狀態(tài)，有一天冷凍期。
狀態(tài)表示為：
- 0 表示不操作
- 1 第一次買入
- 2 第一次賣出
- 3 第一次冷凍期
- 4 第二次買入
- .....
這里是沒有次數(shù)的限制的文章來源地址http://www.zghlxwxcb.cn/news/detail-803718.html
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(4, 0));
dp[0][0] -= prices[0]; // 持股票
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
}
};到了這里，關(guān)于動態(tài)規(guī)劃——買賣股票的最佳時機(jī)系列題Ⅱ的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
