摘要
只買賣一次股票，和不限制次數(shù)地買賣股票彭谁，只是在遞推公式上有差別马靠。而且，這兩種情況都不需要記錄完成買賣的次數(shù)俊戳。
指定了至多買
k次股票渐北，這就暗含著每天的狀態(tài)信息要有買賣股票的次數(shù)歧蒋。
LeetCode123 買賣股票的最佳時(shí)機(jī)III
-
這題和前面兩題買賣股票（代碼隨想錄算法訓(xùn)練營打卡Day49）的區(qū)別還是買賣股票的次數(shù)贸宏。而這題的特點(diǎn)就是我們要控制至多買
2次股票锦聊。- 至多買一次股票，和不限制次數(shù)地買賣股票箩绍，只是在遞推公式上有差別孔庭。而且，這兩種問題都不需要記錄完成買賣的次數(shù)材蛛。
- 但是圆到，至多買
2次股票，這就暗含著每天的狀態(tài)信息要有買賣股票的次數(shù)卑吭。所以芽淡，這道題和前兩題的除了在遞推公式上有差別，在dp數(shù)組的定義上也有差別豆赏。
-
確定
dp數(shù)組及數(shù)組下標(biāo)的含義：-
dp[i][j]表示的是第i天買賣股票可能獲得的最大利潤(rùn)挣菲， -
j == 0表示在第i天或第i天之前第一次買入了股票 -
j == 1表示在第i天或第i天之前第一次賣出了股票 -
j == 2表示在第i天或第i天之前第二次買入了股票 -
j == 3表示在第i天或第i天之前第二次賣出了股票
-
-
確定狀態(tài)轉(zhuǎn)移方程，假設(shè)一開始持有的金額為
0-
對(duì)于第
0天河绽，對(duì)于第一次買賣股票己单，如果買入了股票，只可能是在第
0天時(shí)買入股票耙饰，所以纹笼；如果賣出了股票，只能是第
0天買入后再賣出苟跪，金額不變廷痘，蔓涧。
對(duì)于第二次買賣股票，也同理笋额，如果買入了股票元暴，只可能是在第
0天時(shí)買入股票，所以兄猩；如果賣出了股票茉盏，只能是第
0天買入后再賣出，金額不變枢冤，鸠姨。
-
對(duì)于第
i天，先看第一次買賣- 如果買入了股票淹真，說明在第
i天或之前的某一天第一次買入了股票讶迁。- 如果是在第
i天買入了股票，至少第i-1天時(shí)是未持有股票的核蘸，根據(jù)dp數(shù)組的定義巍糯，第i-1天持有的金額是dp[i-1][1]，那么第i天時(shí)持有的金額為客扎；
- 如果在之前的某一天買入了股票祟峦，現(xiàn)在還應(yīng)該繼續(xù)持有股票，所以
虐唠，保持著持有之前買入的股票的狀態(tài)搀愧。
- 如果是在第
- 如果賣出了股票惰聂，說明在第
i天或之前的某一天第一次賣出了股票疆偿。- 如果是在第
i天買入了股票，至少第i-1天時(shí)是持有股票的搓幌，根據(jù)dp數(shù)組的定義杆故，第i-1天持有的金額是dp[i-1][0]，那么第i天時(shí)持有的金額為溉愁；
- 如果在之前的某一天賣出了股票处铛，第
i天還不應(yīng)該買入股票，所以拐揭，保持之前的狀態(tài)即可
- 如果是在第
- 如果買入了股票淹真，說明在第
-
再看第二次買賣撤蟆，因?yàn)轭}目明確說了不能同時(shí)參與多筆交易，所以第二次買賣必須在第一次買賣完成之后進(jìn)行堂污，所以第二次買入的狀態(tài)是由第一次買賣完成的狀態(tài)（即第一次賣出股票
dp[i - 1][1]）轉(zhuǎn)移來的家肯。-
如果買入了股票，在第
i天或之前的某一天第二次買入了股票盟猖。- 如果是在第
i天買入了股票讨衣，至少第i-1天時(shí)是未持有股票的换棚，可以假設(shè)第i-1天時(shí)已經(jīng)完成了第一次買賣，根據(jù)dp數(shù)組的定義反镇，第i-1天持有的金額是dp[i-1][1]固蚤，那么第i天時(shí)持有的金額為 - 如果在之前的某一天買入了股票歹茶，現(xiàn)在還應(yīng)該繼續(xù)持有股票夕玩，所以
，保持著持有之前買入的股票的狀態(tài)惊豺。
- 如果是在第
-
如果賣出了股票风秤，在第
i天或之前的某一天第二次賣出了股票。- 如果是在第
i天買入了股票扮叨，至少第i-1天時(shí)是持有股票的缤弦，根據(jù)dp數(shù)組的定義，第i-1天持有的金額是dp[i-1][0]彻磁，那么第i天時(shí)持有的金額為 - 如果在之前的某一天賣出了股票，第
i天還不應(yīng)該買入股票衷蜓，所以累提，保持之前的狀態(tài)即可
- 如果是在第
-
狀態(tài)轉(zhuǎn)移方程
-
按推導(dǎo)出的第
0天的狀態(tài)來初始化dp數(shù)組。遍歷順序磁浇，
dp[i][j]的更新依賴于dp[i-1][j]斋陪，所以i應(yīng)該從小到大遍歷，第一次和第二次買賣股票有先后順序置吓，j應(yīng)該從小到大更新无虚。
題解代碼如下
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
dp[0][0] = 0 - prices[0];
dp[0][1] = 0;
dp[0][2] = 0 - prices[0];
dp[0][3] = 0;
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], 0 - prices[i]);
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]);
}
return dp[prices.size() - 1].back();
}
};
LeetCode188 買賣股票的最佳時(shí)機(jī)IV
這題的解法其實(shí)就是動(dòng)態(tài)地控制“買賣股票的最佳時(shí)機(jī)III”的中的最多買賣次數(shù)。最多買賣次數(shù)從兩次變成了
k次衍锚，實(shí)際上就是添加一個(gè)循環(huán)來表示從第j - 1次買賣到第j次買賣的狀態(tài)轉(zhuǎn)移友题。-
確定
dp數(shù)組及數(shù)組下標(biāo)的含義：-
dp[i][j]表示的是第i天買賣股票可能獲得的最大利潤(rùn)，j為0或偶數(shù)時(shí)表示第j%2+1次持有股票戴质，j為奇數(shù)時(shí)表示第j%2+1次賣出股票度宦。
-
-
確定狀態(tài)轉(zhuǎn)移方程，關(guān)鍵在于每次買賣之間的狀態(tài)轉(zhuǎn)移
- 第
0天的初始化要注意告匠，不能只初始化第一次買賣的狀態(tài)戈抄，每次買賣都要初始化，
- 對(duì)于第
i天后专，如果是第一次買賣划鸽，假設(shè)一開始持有的金額為0
- 對(duì)于第
i天，如果不是第一次買賣行贪，假設(shè)當(dāng)前是第j%2+1次買賣漾稀，則第i天第j%2+1次買賣的買賣是由已經(jīng)完成了j-1次買賣的狀態(tài)轉(zhuǎn)移來的
- 第
初始狀態(tài)就是第
0天的狀態(tài)模闲，按第0天的狀態(tài)初始化dp數(shù)組。遍歷順序的道理和上一題相同崭捍，
i從小到大遍歷尸折，j也從小到大遍歷。
題解代碼如下
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));
for (int j = 0; j < 2 * k; j += 2) {
dp[0][j] = 0 - prices[0];
}
for (int i = 1; i < prices.size(); i++) {
for (int j = 0; j < 2 * k; j += 2) {
// 判斷一下是不是第一次買賣股票殷蛇，防止數(shù)組下標(biāo)越界
if (j == 0) dp[i][j] = max(dp[i - 1][j], 0 - prices[i]);
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k - 1];
}
};
