总结股票买卖问题，所有case都化简为DP处理。

通解

i 代表 ith day
k 代表最大交易次数
0/1 代表手中是否持有股票

T【i】【k】【0】 代表 在ith day 最多k次交易，ith day结束后不持有股票的 profit
T【i】【k】【1】 代表 在ith day 最多k次交易，ith day结束后持有股票的 profit

那么base case
T【-1】【k】【0】 = 0 （1）
T【-1】【k】【1】 = -INF （2）
T【i】【0】【0】 = 0 （3）
T【i】【0】【1】= -INF （4）
递推关系
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k-1】【0】- prices【i】）#买入

（只有买入操作消耗交易次数）

应用

K=1

T【i】【1】【0】=max（T【i-1】【1】【0】，T【i-1】【1】【1】+prices【i】）
T【i】【1】【1】=max（T【i-1】【1】【1】，T【i-1】【0】【0】-prices【i】）
因为（3）
所以
T【i】【1】【0】=max（T【i-1】【1】【0】，T【i-1】【1】【1】+prices【i】）
T【i】【1】【1】=max（T【i-1】【1】【1】，-prices【i】）

public int maxProfit(int[] prices) {
    int T_i10 = 0, T_i11 = Integer.MIN_VALUE;
        
    for (int price : prices) {
        T_i10 = Math.max(T_i10, T_i11 + price);
        T_i11 = Math.max(T_i11, -price);
    }
        
    return T_i10;
}

K=INF

K无穷大时候，K和K-1 没区别
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k-1】【0】- prices【i】）#买入
变成
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k】【0】- prices【i】）#买入

public int maxProfit(int[] prices) {
    int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price);
        T_ik1 = Math.max(T_ik1, T_ik0_old - price);
    }
    
    return T_ik0;
}

K=2

T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k-1】【0】- prices【i】）#买入
变成
T【i】【2】【0】 = max（T【i-1】【2】【0】，T【i-1】【2】【1】+prices【i】）
T【i】【2】【1】 = max（T【i-1】【2】【1】，T【i-1】【1】【0】- prices【i】）
T【i】【1】【0】 = max（T【i-1】【1】【0】，T【i-1】【1】【1】+prices【i】）
T【i】【1】【1】 = max（T【i-1】【1】【1】，- prices【i】）

public int maxProfit(int[] prices) {
    int T_i10 = 0, T_i11 = Integer.MIN_VALUE, T_i20 = 0, T_i21 = Integer.MIN_VALUE;
        
    for (int price : prices) {
        T_i20 = Math.max(T_i20, T_i21 + price);
        T_i21 = Math.max(T_i21, T_i10 - price);
        T_i10 = Math.max(T_i10, T_i11 + price);
        T_i11 = Math.max(T_i11, -price);
    }
        
    return T_i20;
}

K 是任何数

T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k-1】【0】- prices【i】）#买入

public int maxProfit(int k, int[] prices) {
    //如果K 大于等于Prices长度的一半，那么相当于K=INF的情况
    if (k >= prices.length >>> 1) {
        int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
        for (int price : prices) {
            int T_ik0_old = T_ik0;
            T_ik0 = Math.max(T_ik0, T_ik1 + price);
            T_ik1 = Math.max(T_ik1, T_ik0_old - price);
        }
    
        return T_ik0;
    }
        
    int[] T_ik0 = new int[k + 1];
    int[] T_ik1 = new int[k + 1];
    Arrays.fill(T_ik1, Integer.MIN_VALUE);
        
    for (int price : prices) {
        for (int j = k; j > 0; j--) {
            T_ik0[j] = Math.max(T_ik0[j], T_ik1[j] + price);
            T_ik1[j] = Math.max(T_ik1[j], T_ik0[j - 1] - price);
        }
    }
        
    return T_ik0[k];
}

K=INF with Cooldown

T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k-1】【0】- prices【i】）#买入
当K=INF变为
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k】【0】- prices【i】）#买入
但是有cooldown时候，变为
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-2】【k】【0】- prices【i】）#买入
因为不能在i天买入如果股票是在i-1天卖出的，所以只能用T【i-2】【k】【0】

public int maxProfit(int[] prices) {
    int T_ik0_pre = 0, T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price);
        T_ik1 = Math.max(T_ik1, T_ik0_pre - price);
        T_ik0_pre = T_ik0_old;
    }
    
    return T_ik0;
}

K=INF with Transaction Fee

T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k-1】【0】- prices【i】）#买入
当K=INF变为
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k】【0】- prices【i】）#买入
但是有Fee时候，变为因为fee只在卖出时候付清
T【i】【k】【0】 = max（T【i-1】【k】【0】，T【i-1】【k】【1】+prices【i】-fee） #卖出
T【i】【k】【1】 = max（T【i-1】【k】【1】，T【i-1】【k】【0】- prices【i】）#买入

public int maxProfit(int[] prices, int fee) {
    long T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        long T_ik0_old = T_ik0;
        T_ik0 = Math.max(T_ik0, T_ik1 + price - fee);
        T_ik1 = Math.max(T_ik1, T_ik0_old - price);
    }
        
    return (int)T_ik0;
}