Java通过动态规划设计股票买卖最佳时机

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

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

dp[0][0] = -price[0]
dp[0][1] = 0

    // 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        // dp 表示当天能获得的最大利润
        int[][] dp = new int[prices.length][2]; // 对每一天来说，就两个状态，一个是买入，一个是卖出
        dp[0][0] = -prices[0]; // 第一天买入
        dp[0][1] = 0; // 第一天卖出
        for(int i=1; i<prices.length; 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[prices.length-1][1];
    }

   // 买卖股票的最佳时机2 —— 可以多次买入和卖出，但是注意每次只能持有一张股票，就是必须是 买 - 卖 - 买 - 卖 - 买 - 卖 ....这种顺序
    public int maxProfit2(int[] prices) {
        // 本题与上题的区别就在于状态转移方程不同 -- 本题可以用之前得到的利润 (即 dp[i-1][1]，上一轮卖出后剩下的钱) 再去买入，而上一题必须 0-price[i] 买入
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]); ---- 买入股票能得到的最大利润状态转移方程有变化
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1; i<prices.length; 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[prices.length-1][1];
    }

   // 买卖股票的最佳时机3 —— 本题与上一题的区别在于，本题只能执行两次买入、卖出操作
    public int maxProfit3(int[] prices) {
        // 每次可执行的操作状态为 ，第一次买入、第一次卖出、第二次买入、第二次卖出，因此 dp 定义为
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for(int i=1; i<prices.length; 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]);
            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]);
        }
        return dp[prices.length-1][3];
    }

    // 买卖股票的最佳时期 —— 最多进行 K 次交易
    public int maxProfit(int k, int[] prices) {
        // 就是两次交易的升级版
        int[][] dp = new int[prices.length][2*k 1]; // 奇数表示买入，偶数表示卖出
        // 初始化
        for(int j=1; j<2*k; j =2){
            dp[0][j] = -prices[0];
        }
        for(int i=1; i<prices.length; 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[prices.length-1][2*k];
    }

   // 买卖股票含冷冻期
    public int maxProfit(int[] prices) {
        // 一共四种状态 买入 卖出（早就卖出保存卖出态，当天卖出） 冷冻
        int dp[][] = new int[prices.length][4];
        // 初始化
        dp[0][0] = -prices[0];
        for(int i=1; i<prices.length; i  ){
            // 买入状态 —— 前一天就是买入状态   前一天是卖出状态今天买入了   前一天是冷冻状态今天买入了
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][3]-prices[i], dp[i-1][2]-prices[i]) );
            // 卖出态1 —— 前一天就是卖出态1   前一天是冷冻态
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);
            // 卖出态2 —— 当天卖出了
            dp[i][2] = dp[i-1][0]   prices[i];
            // 冷冻态 —— 前一天是卖出态2
            dp[i][3] = dp[i-1][2];
        }
        return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));
    }

    // 买卖股票的最佳时机，含手续费
    public int maxProfit2(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        // 初始化
        dp[0][0] = -prices[0] - fee;
        for(int i=1; i<prices.length; i  ){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i] - fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]   prices[i]);
        }
        return dp[prices.length-1][1];
    }