解题思路分析
利用三维DP数组来构建状态关系dp[n+1][k+1][2]
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
第i天不持有股票:第i-1天就不持有,或者第i-1天持有,又卖了
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
第i天持有股票:第i-1天就持有,或者第i-1天不持有,第i天买入了
base case:
当i=0时,等价于第0天,还没有开始。则不持有的收益为0.持有的状态不可能,用最小值来表示收益代表不可能
121. 买卖股票的最佳时机
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
图片说明

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if(n<2) return 0;//无法完成交易
        /* k=1;
        dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                   =max(dp[i-1][1][0],dp[i-1][1][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][1][1],dp[i-1][1-1=0][0]-prices[i]);---在buy时令操作数k-1
        */
        int[][] dp=new int[n+1][2];
        //base case:第0天不持有股票收益为0,不可能持有股票,用最小数代替
        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){//注意dp的i不是prices的i
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i-1]);
        }
        return dp[n][0];
    }
}

122. 买卖股票的最佳时机 II
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
图片说明

class Solution {
    public int maxProfit(int[] prices) {
        /* k=无数大(可以视k=k-1);
        dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                   =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]);---在buy时令操作数k-1
        省去k坐标
        */
        int n=prices.length;
        if(n<2) return 0;
        int[][] dp=new int[n+1][2];
        //base case:
        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
        }
        return dp[n][0];      
    }
    public int maxProfit1(int[] prices) {
        int n=prices.length;
        if(n < 2) return 0;
        int ans=0;
        for(int i=1;i<n;i++){
            int diff=prices[i]-prices[i-1];
            if(diff>0){
                ans+=diff;
            }
        }
        return ans;
    }
}

123. 买卖股票的最佳时机 III
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
图片说明

class Solution {
    public int maxProfit(int[] prices) {
    /* k=2;1:没有股票,2:有股票
        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]);---在buy时令操作数k-1
       我们可以穷举k的取值
    */
        int n=prices.length;
        if(n<2) return 0;
        int[][][] dp=new int[n+1][2][2];
        //base case:
        dp[0][0][0]=dp[0][1][0]=0;
        dp[0][0][1]=dp[0][1][1]=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            dp[i][0][0]=Math.max(dp[i-1][0][0],dp[i-1][0][1]+prices[i-1]);//-buy
            dp[i][0][1]=Math.max(dp[i-1][0][1],-prices[i-1]);
            dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i-1]);//-buy
            dp[i][1][1]=Math.max(dp[i-1][1][1],dp[i-1][0][0]-prices[i-1]);
        }
        return dp[n][1][0];
    }

    //优化代码--只和相邻状态有关,则记录相邻状态
    public int maxProfit1(int[] prices) {
        int n=prices.length;
        int buy1=-prices[0],sell1=0;
        int buy2=-prices[0],sell2=0;
        for(int i=1;i<n;i++){
            buy1=Math.max(buy1,-prices[i]);
            sell1=Math.max(sell1,buy1+prices[i]);
            buy2=Math.max(buy2,sell1-prices[i]);
            sell2=Math.max(sell2,buy2+prices[i]);
        }
        return sell2;
    }
}

188. 买卖股票的最佳时机 IV
给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
图片说明

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n=prices.length;
        if(n < 2) return 0;
        //k如果可以超过n/2,则和k为无穷大效果一样,用辅助函数求解
        if(k > n/2) return maxProfit_help(prices);
        //借助于三维DP来解决
        int[][][] dp=new int[n+1][k+1][2];
        //base case:处理i=0的情况
        for(int i=1;i<=k;i++){
            dp[0][i][0]=0;
            dp[0][i][1]=Integer.MIN_VALUE;
        }
        for(int i=1;i<=n;i++){
            for(int j=k;j>=1;j--){
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
            }
        }
        return dp[n][k][0];

    }
    public int maxProfit_help(int[] prices) {
        /* k=无数大(可以视k=k-1);
        dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                   =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]);---在buy时令操作数k-1
        省去k坐标
        */
        int n=prices.length;
        if(n<2) return 0;
        int[][] dp=new int[n+1][2];
        //base case:
        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
        }
        return dp[n][0];      
    }
}

** 309. 最佳买卖股票时机含冷冻期**
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
图片说明

class Solution {
    public int maxProfit(int[] prices) {
        /* k=无穷大;1:没有股票,2:有股票
            dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);-sell
            dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
            含冷冻期则在买入时,和一天前的情况有关
            即:
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);-sell
            dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i]);
        */
        int n=prices.length;
        if(n < 2) return 0;
        int[][] dp=new int[n+1][2];
        //base case:列举第0天和第1天(因为冷冻期一天)
        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;
        dp[1][0]=0;
        dp[1][1]=-prices[0];
        for(int i=2;i<=n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i-1]);
        }
        return dp[n][0];
    }
}

714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        /* k=无穷大;1:没有股票,2:有股票
            dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);-sell
            dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);---在buy时令操作数k-1
            含手续费则在买入时,收益减去手续费
            即:
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);-sell
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);
        */
        int n=prices.length;
        if(n < 2) return 0;
        int[][] dp=new int[n+1][2];
        //base case:
        dp[0][0]=0;
        dp[0][1]=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]-fee);
        }
        return dp[n][0];
    }
}