買賣股票的最佳時機系列題目是leetcode的經(jīng)典系列題目杨名。對于這系列題目可以用一種思想解決之渐北，也就是DP狀態(tài)轉(zhuǎn)移思想。
本筆記收錄了Leetcode上的一個題解：一個方法團滅 6 道股票問題.
但其實通解有時不是很直觀，所以同時也記錄對于這系列問題的特解和有趣的思想艾猜。

一衬鱼、通用解法思想

（1）狀態(tài)：

這個系列問題的「狀態(tài)」有三個业筏，第一個是天數(shù)，第二個是允許交易的最大次數(shù)鸟赫，第三個是當(dāng)前的持有狀態(tài)（即之前說的 rest 的狀態(tài)蒜胖，我們不妨用 1 表示持有，0 表示沒有持有）抛蚤。然后我們用一個三維數(shù)組就可以裝下這幾種狀態(tài)的全部組合：

dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 為天數(shù)台谢，大 K 為最多交易數(shù)
此問題共 n × K × 2 種狀態(tài)，全部窮舉就能搞定岁经。
for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

（2）狀態(tài)轉(zhuǎn)移：

狀態(tài)轉(zhuǎn)移

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   選擇 rest  ,           選擇 sell      )

解釋：今天我沒有持有股票对碌，有兩種可能：
要么是我昨天就沒有持有，然后今天選擇 rest蒿偎，所以我今天還是沒有持有朽们；
要么是我昨天持有股票怀读，但是今天我 sell 了，所以我今天沒有持有股票了骑脱。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   選擇 rest  ,           選擇 buy         )

解釋：今天我持有著股票菜枷，有兩種可能：
要么我昨天就持有著股票，然后今天選擇 rest叁丧，所以我今天還持有著股票啤誊；
要么我昨天本沒有持有，但今天我選擇 buy拥娄，所以今天我就持有股票了蚊锹。

（3）基態(tài)：

有了狀態(tài)轉(zhuǎn)移方程后，我們還需要一個基態(tài)稚瘾，從這個基態(tài)依靠這些方程推出每個狀態(tài)的結(jié)果牡昆。

base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

狀態(tài)轉(zhuǎn)移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

二、題目解法：

1. 買賣股票的最佳時機

K=1 通用解法：

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) 
            = max(dp[i-1][1][1], -prices[i])
解釋：k = 0 的 base case摊欠，所以 dp[i-1][0][0] = 0丢烘。

現(xiàn)在發(fā)現(xiàn) k 都是 1，不會改變些椒，即 k 對狀態(tài)轉(zhuǎn)移已經(jīng)沒有影響了播瞳。
可以進行進一步化簡去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])

for (int i = 0; i < n; i++) {
    if (i - 1 == -1) {
        dp[i][0] = 0;
        // 解釋：
        //   dp[i][0] 
        // = max(dp[-1][0], dp[-1][1] + prices[i])
        // = max(0, -infinity + prices[i]) = 0
        dp[i][1] = -prices[i];
        //解釋：
        //   dp[i][1] 
        // = max(dp[-1][1], dp[-1][0] - prices[i])
        // = max(-infinity, 0 - prices[i]) 
        // = -prices[i]
        continue;
    }
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];

通解簡化：

// k == 1
int maxProfit_k_1(int[] prices) {
    int n = prices.length;
    // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i-1][1], -prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0;
}

特解：

var maxProfit = function(prices) {
    // 維護一個最小值
    // 維護一個maxProfit
    let min = prices[0], maxProfit = 0
    for(const price of prices) {
        if(price < min) {
            min = price
        } else {
            if(price - min > maxProfit) {
                maxProfit = price - min
            }
        }
    }
    return maxProfit
};

2. 買賣股票的最佳時機 II

K=+Inf 通用解法：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
            = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])

我們發(fā)現(xiàn)數(shù)組中的 k 已經(jīng)不會改變了(k是無窮大 k-1近似于k)，也就是說不需要記錄 k 這個狀態(tài)了：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

int maxProfit_k_inf(int[] prices) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0; // 因為dp_i_1需要的是上個狀態(tài)的dp_i_0
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
    }
    return dp_i_0;
}

特解：每次只要是上升都買和賣免糕，這樣就可以無限獲利

var maxProfit = function(prices) {
    let profit = 0
    for(let i=0;i+1<prices.length;i++) {
        if(prices[i]<prices[i+1]) {
            profit += (prices[i+1]-prices[i])
        }
    }
    return profit
};

3. 最佳買賣股票時機含冷凍期

K=+Inf with cooldown 通解：
每次 sell 之后要等一天才能繼續(xù)交易赢乓。只要把這個特點融入上一題的狀態(tài)轉(zhuǎn)移方程即可：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解釋：第 i 天選擇 buy 的時候，要從 i-2 的狀態(tài)轉(zhuǎn)移石窑，而不是 i-1 牌芋。

int maxProfit_with_cool(int[] prices) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    int dp_pre_0 = 0; // 代表 dp[i-2][0]
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        dp_pre_0 = temp;
    }
    return dp_i_0;
}

4. 買賣股票的最佳時機含手續(xù)費

K=+Inf with fee：
每次交易要支付手續(xù)費，只要把手續(xù)費從利潤中減去即可尼斧。改寫方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
解釋：相當(dāng)于買入股票的價格升高了。
在第一個式子里減也是一樣的试吁，相當(dāng)于賣出股票的價格減小了棺棵。

int maxProfit_with_fee(int[] prices, int fee) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
    }
    return dp_i_0;
}

5. 買賣股票的最佳時機 III

K=2：
這道題 k = 2 和后面要講的 k 是任意正整數(shù)的情況中，對 k 的處理就凸顯出來了熄捍。我們直接寫代碼烛恤，邊寫邊分析原因。

原始的動態(tài)轉(zhuǎn)移方程余耽，沒有可化簡的地方
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

int max_k = 2;
int[][][] dp = new int[n][max_k + 1][2];
for (int i = 0; i < n; i++) {
    for (int k = max_k; k >= 1; k--) {
        if (i - 1 == -1) { /*處理 base case */ }
        dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
        dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
    }
}
// 窮舉了 n × max_k × 2 個狀態(tài)缚柏，正確。
return dp[n - 1][max_k][0];碟贾。

這里 k 取值范圍比較小币喧，所以可以不用 for 循環(huán)轨域，直接把 k = 1 和 2 的情況手動列舉出來也可以：

dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[i])

int maxProfit_k_2(int[] prices) {
    int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
    int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
    for (int price : prices) {
        dp_i20 = Math.max(dp_i20, dp_i21 + price);
        dp_i21 = Math.max(dp_i21, dp_i10 - price);
        dp_i10 = Math.max(dp_i10, dp_i11 + price);
        dp_i11 = Math.max(dp_i11, -price);
    }
    return dp_i20;
}

6. 買賣股票的最佳時機 IV

K = Any integer
有了上一題 k = 2 的鋪墊，這題應(yīng)該和上一題的第一個解法沒啥區(qū)別杀餐。但是出現(xiàn)了一個超內(nèi)存的錯誤干发，原來是傳入的 k 值會非常大，dp 數(shù)組太大了∈非蹋現(xiàn)在想想枉长，交易次數(shù) k 最多有多大呢？
一次交易由買入和賣出構(gòu)成琼讽，至少需要兩天必峰。所以說有效的限制 k 應(yīng)該不超過 n/2，如果超過钻蹬，就沒有約束作用了吼蚁，相當(dāng)于 k = +infinity。這種情況是之前解決過的脉让。
直接把之前的代碼重用：

int maxProfit_k_any(int max_k, int[] prices) {
    int n = prices.length;
    if (max_k > n / 2) 
        return maxProfit_k_inf(prices);

    int[][][] dp = new int[n][max_k + 1][2];
    for (int i = 0; i < n; i++) 
        for (int k = max_k; k >= 1; k--) {
            if (i - 1 == -1) { /* 處理 base case */ }
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);     
        }
    return dp[n - 1][max_k][0];
}