Leetcode121宗兼，股票只能買賣一次，問(wèn)最大利潤(rùn)。
示例 :
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入垂攘，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出筋讨，最大利潤(rùn) = 6-1 = 5 。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格派任；同時(shí)砸逊，你不能在買入前賣出股票。
思路分析：
法1：雙指針：定義雙指針掌逛，一個(gè)指向買入师逸，一個(gè)指向賣出，遍歷數(shù)組豆混，更新最大值篓像。
法2：貪心：因?yàn)橹挥幸淮钨I入賣出，保證以最低的價(jià)錢買入皿伺，然后遍歷數(shù)組员辩，更新最大值。
法3：動(dòng)態(tài)規(guī)劃：一天只有兩個(gè)狀態(tài)：持有和不持有鸵鸥，遍歷數(shù)組返回最后一天的情況
-
dp[i][0]和dp[i][1]分別代表第i天持有和不持有股票所得的現(xiàn)金奠滑。 - 狀態(tài)轉(zhuǎn)移方程：對(duì)于當(dāng)前填持有和不持有，我們分別分析其上一天的情況
- 持有狀態(tài)妒穴，上一天持有或不持有（
現(xiàn)在買入宋税，即-prices[i]）最大值； - 不持有狀態(tài)讼油，上一天可以是持有（
現(xiàn)在賣了杰赛，即prices[i - 1][0] + prices[i]）或不持有最大值。
- 持有狀態(tài)妒穴，上一天持有或不持有（
代碼實(shí)現(xiàn)：代碼1：雙指針
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int start = 0, end = 1, max = 0;
while (start < end && end < prices.length) {
if (prices[start] >= prices[end]) {
start = end++;
} else {
max = Math.max(max, prices[end] - prices[start]);
end++;
}
}
return max;
}
代碼2：貪心
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int low = Integer.MAX_VALUE;
int max = 0;
for (int i = 0; i < prices.length; ++i) {
low = Math.min(low, prices[i]);
max = Math.max(max, prices[i] - low);
}
return max;
}
代碼3：動(dòng)態(tài)規(guī)劃
public int maxProfit(int[] prices) {
int len = prices.length;
if (prices == null || len == 0) return 0;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
Leetcode122矮台，可以多次買賣股票乏屯，問(wèn)最大收益根时。
示例：
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 瓶珊。
隨后啸箫，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 伞芹。
思路分析：
法1：貪心算法：實(shí)現(xiàn)上述需求每次交易只要買入小于賣出忘苛，即保證每次交易都有收益即可！
法2：動(dòng)態(tài)規(guī)劃：這里與上題唯一的區(qū)別是多次買賣股票唱较。關(guān)鍵點(diǎn)：
當(dāng)
dp[i][0]扎唾，即第i天持有股票時(shí)，是在之前利潤(rùn)（前一天賣出的最大利潤(rùn)南缓，前一天必須賣出）基礎(chǔ)上在買入胸遇，即dp[i - 1][1] - prices[i]。汉形，上題只有一次買入纸镊。對(duì)于第i天不持有股票，與上邊相同概疆。
代碼實(shí)現(xiàn)：代碼1：貪心
public int maxProfit(int[] prices) {
int n = prices.length;
if (prices == null || n == 0) return 0;
int max = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
max += prices[i] - prices[i - 1];
}
}
return max;
}
代碼2：動(dòng)態(tài)規(guī)劃
public int maxProfit(int[] prices) {
int len = prices.length;
if (prices == null || len == 0) return 0;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
Leetcode123逗威，最多買賣兩次，問(wèn)最大收益岔冀。
示例 :
輸入: [3,3,5,0,0,3,1,4]
輸出: 6
解釋: 在第 4 天（股票價(jià)格 = 0）的時(shí)候買入凯旭，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 3-0 = 3 使套。
隨后罐呼，在第 7 天（股票價(jià)格 = 1）的時(shí)候買入，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣出侦高，這筆交易所能獲得利潤(rùn) = 4-1 = 3 嫉柴。
思路分析：
與案例2不同的是，本例限制買入賣出的次數(shù)矫膨，最多買入兩次差凹。相對(duì)來(lái)說(shuō)，難度大了很多侧馅。對(duì)于下面的情況：
1 5 2 8 3 10
第一天買第二天賣危尿，第三天買第四天賣，第五天買第六天賣馁痴，三次收益分別是 4谊娇，6，7，最高的兩次就是 6 + 7 = 13 了济欢，但是我們第二天其實(shí)可以不賣出赠堵，第四天再賣出，那么收益是 8 - 1 = 7法褥，再加上第五天買入第六天賣出的收益就是 7 + 7 = 14了茫叭。
所以當(dāng)達(dá)到了一個(gè)高點(diǎn)時(shí)不一定要賣出！０氲取揍愁！---用動(dòng)態(tài)規(guī)劃（動(dòng)態(tài)規(guī)劃關(guān)鍵就是數(shù)組定義和狀態(tài)轉(zhuǎn)移方程！Ｉ倍ＣФ凇）
法1：動(dòng)態(tài)規(guī)劃：當(dāng)然我們可以暴力的想一下，當(dāng)我們計(jì)算第 i 天的收益時(shí)進(jìn)行了k次交易切距，我們可以選擇：
不買入賣出朽缎，即第
i天的收益 等于第i - 1天的收益.賣出，追求更大收益谜悟，這里就要在
0到i-1天就要選擇一天買入话肖。多選擇了一次買入，那在買入之前已經(jīng)進(jìn)行了k-1次買賣葡幸。
即：當(dāng)用 dp[i][k] 表示前i天最多交易k次的最高收益（數(shù)組定義）狼牺，求解可分為兩部分（狀態(tài)轉(zhuǎn)移）
不操作：
dp[i][k] = dp[i-1][k]之前有買入：在第 j 天買入，收益就是
prices[i] - （prices[j] - dp[j][k-1]）礼患，我們利用動(dòng)態(tài)規(guī)劃找第j天（prices[j] - dp[j][k-1]）最小值，即代碼中的min
法2：狀態(tài)機(jī)掠归，一共有五種狀態(tài)：不操作缅叠，第一次買入/賣出和第二次買入/賣出。
-
dp[i][j]表示第i天虏冻，狀態(tài)為j所剩最大現(xiàn)金肤粱。，注：dp[i][j]中 i表示第i天厨相，j為 [0 - 4] 五個(gè)狀態(tài) - 對(duì)于i天都有兩個(gè)狀態(tài)：持有和不持有领曼，我們分別考慮前一天的狀態(tài)。參照122題求解蛮穿，只不過(guò)我們進(jìn)行兩次這樣的操作庶骄。
代碼實(shí)現(xiàn)：代碼1：動(dòng)態(tài)規(guī)劃
public int maxProfit(int[] prices) {
int n = prices.length;
if (prices == null || n == 0) return 0;
int K = 2;
int[][] dp = new int[n][K + 1];
for (int k = 1; k <= K; k++) {
int min = prices[0];
for (int i = 1; i < n; i++) {
//找出第 1 天到第 i 天 prices[buy] - dp[buy][k - 1] 的最小值
min = Math.min(prices[i] - dp[i][k - 1], min);
//比較不操作和選擇一天買入的哪個(gè)值更大
dp[i][k] = Math.max(dp[i - 1][k], prices[i] - min);
}
}
return dp[n - 1][K];
}
代碼2：狀態(tài)機(jī)
public int maxProfit(int[] prices) {
int n = prices.length;
if (prices == null || n == 0) return 0;
int[][] dp = new int[n][5];
dp[0][1] = dp[0][3] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - 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[n - 1][4];
}
Leetcode188，最多買賣K次践磅，問(wèn)最大收益单刁。
示例 :
輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價(jià)格 = 2) 的時(shí)候買入，在第 2 天 (股票價(jià)格 = 4) 的時(shí)候賣出府适，這筆交易所能獲得利潤(rùn) = 4-2 = 2 羔飞。
思路分析：動(dòng)態(tài)規(guī)劃：無(wú)論買賣多少次肺樟，每天我們都對(duì)應(yīng)兩個(gè)狀態(tài)。我們這里使用123中狀態(tài)機(jī)的解法：
-
dp[i][j] 表示第i天逻淌，狀態(tài)為j么伯，所剩下的最大現(xiàn)金是dp[i][j]。 - j的狀態(tài)表示為：0 表示不操作卡儒；1 第一次買入田柔，2 第一次賣出；3 第二次買入朋贬，4 第二次賣出... 即除了0之外凯楔，奇數(shù)狀態(tài)買入，偶數(shù)狀態(tài)賣出锦募。
- 注意j的步長(zhǎng)為2（每天）摆屯，共進(jìn)行2*k次買入賣出，注意j循環(huán)時(shí)不要越界糠亩！測(cè)試用例中含有0虐骑，特判！
狀態(tài)轉(zhuǎn)移方程為：
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]);
- 注意初始條件：當(dāng)賣出赎线，即
dp[0][j] == 0, j為偶數(shù)廷没；當(dāng)買入，即dp[0][j] = -prices[0]垂寥，j為奇數(shù)颠黎。 - 按照定義最終有2k個(gè)狀態(tài)，所以返回
dp[n - 1][2 * k]滞项。
時(shí)間復(fù)雜度：O(KN)狭归，K為交易的次數(shù)。
代碼實(shí)現(xiàn)：
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (prices == null || n == 0) return 0;
int[][] dp = new int[n][2 * k + 1];
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[n - 1][2 * k];
}
Leetcode309文判， 可以多次買賣但每次賣出有冷凍期1天过椎。
示例 :
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
思路分析：動(dòng)態(tài)規(guī)劃：本題在122基礎(chǔ)上加入冷凍期，這里我們第i天分為三種狀態(tài)戏仓，分別用0~2表示：
持有股票：可能是前一天就持有或者度過(guò)冷凍期又買入（不能直接買入）的最大值疚宇。
不持有股票，處于冷凍期：原因是當(dāng)前賣出了股票赏殃，得到收益敷待。
不持有股票，不在冷凍期：可能前一天在冷凍期或者不在冷凍期的最大值嗓奢。
注意：最后我們需要返回不持有股票的最大值讼撒。
代碼實(shí)現(xiàn)：
public int maxProfit(int[] prices) {
int n = prices.length;
if (prices == null || n == 0) return 0;
int[][] dp = new int[n][3];
dp[0][0] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
// 不持有股票
dp[i][1] = dp[i - 1][0] + prices[i];
dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
}
return Math.max(dp[n - 1][1], dp[n - 1][2]);
}
Leetcode714， 可以多次買賣，但每次有手續(xù)費(fèi)根盒。
示例 :
輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達(dá)到的最大利潤(rùn):
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤(rùn): ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
思路分析：本題在122基礎(chǔ)上加入手續(xù)費(fèi)钳幅，我們只需要在每次賣出時(shí)減去手續(xù)費(fèi)即可（即需要支付手續(xù)費(fèi)）！
代碼實(shí)現(xiàn)：
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
if (prices == null || n == 0) return 0;
int[][] dp = new int[n][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return dp[n - 1][1];
}
