123.買賣股票的最佳時(shí)機(jī)III
題目鏈接/文字講解：買賣股票的最佳時(shí)機(jī)III
題設(shè)：給定一個(gè)數(shù)組攘乒，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格亩码。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)姐帚。你最多可以完成 兩筆 交易蛹尝。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
思路：動(dòng)規(guī)五部曲：
1.dp數(shù)組含義：一天一共就有五個(gè)狀態(tài)叹侄，
- 沒有操作 （其實(shí)我們也可以不設(shè)置這個(gè)狀態(tài)）
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
dp[i][j]中 i表示第i天辨绊，j為 [0 - 4] 五個(gè)狀態(tài)敞咧，dp[i][j]表示第i天狀態(tài)j所剩最大現(xiàn)金。
2.根據(jù)每個(gè)數(shù)組含義偶翅，去推導(dǎo)相應(yīng)的遞歸表達(dá)式默勾。
3.dp數(shù)組初始化：根據(jù)每個(gè)數(shù)組含義初始化dp[0][i]即可。
4.遍歷順序：從前往后遍歷聚谁。
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][5];
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[len - 1][4];
}
}
188.買賣股票的最佳時(shí)機(jī)IV
題目鏈接/文字講解：買賣股票的最佳時(shí)機(jī)IV
題設(shè)：給定一個(gè)整數(shù)數(shù)組 prices 母剥，它的第 i 個(gè)元素 prices[i] 是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)垦巴。你最多可以完成 k 筆交易媳搪。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
