股票买卖问题是动态规划的经典问题，为此我对该题型进行分析。

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

分析
该题的主要是找一个最大攀升高度，这个攀升高度和最大高低差的含义是有区别的，有方向性，也就是说找一个较低点，在较低点之后找一个较高点，这个高低即为利润。

动态规划的思想：设定第i天的兜里的钱为dp，分别存在持股和费持股两种状态，故设定0为非持股状态，1为持股状态。

第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]);
再给动态规划增加一个维度,来记录买入的次数
dp[第几天][是否持有][买入几次];

实现如下

class Solution {
    public int maxProfit(int[] prices) {
        int[][][] dp=new int[prices.length][2][2];//第几天，持有，买入次数
        dp[0][0][0]=0;
        dp[0][0][1]=-10001;//非法数据
        dp[0][1][0]=-10001;//非法数据
        dp[0][1][1]=-prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i][0][0]=dp[i-1][0][0];
            dp[i][0][1]=Math.max(dp[i-1][0][1],dp[i-1][1][1]+prices[i]);//今天卖
            dp[i][1][0]=-10001;//交易次数为0，但是持有？做梦呢
            dp[i][1][1]=Math.max(dp[i-1][1][1],dp[i-1][0][0]-prices[i]);//今天买
            
        }
        int lastIdx=prices.length-1;
        return Math.max(dp[lastIdx][0][1],dp[lastIdx][0][0]);
    }
}

// NOTE: -10001是我设定的非法值，因为在题中当天price范围未0 <= prices[i] <= 10e5 

优化

1.观察一下代码，每次计算都只有 i 和 i-1天的数据，因此可以通过和4个变量记录昨天的，4个变量记录今天的。pre1...4,cur1...4。置换一下继续下一轮。这边不再赘述。

2.贪心算法

不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解。

class Solution {
    public int maxProfit(int[] prices) {
        int max_price=0,min_privce=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min_privce){
                min_privce=prices[i];
            }
            // 在计算利润的时候，以上一个最小值为买入金额。
            max_price=Math.max(max_price,prices[i]-min_privce);
        }
        return max_price;
    }
}

122. 买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析

这题更加简单了，没有交易次数的限制，直接上代码

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[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][0];
    }
}

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

也是跟题1一样的手法，记录持有状态和交易次数

class Solution {
    public int maxProfit(int[] prices) {
        int[][][] dp = new int[prices.length][2][3];// day,是否持有，购买过几次
        dp[0][0][0] = 0;
        dp[0][0][1] = -10001;
        dp[0][0][2] =  -10001;
        dp[0][1][0] =  -10001;
        dp[0][1][1] = -prices[0];
        dp[0][1][2] =  -10001;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0][0] = dp[i - 1][0][0];//没买过，肯定之前也没买过
            dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][1][1] + prices[i]);//未操作，或者今天卖，买过一次
            dp[i][0][2] = Math.max(dp[i - 1][0][2], dp[i - 1][1][2] + prices[i]);//未操作，或者今天卖，买过两次
            dp[i][1][0] =  -10001;// 不可能没买过就持有
            dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]);//未操作，或者今天买，第一次买
            dp[i][1][2] = Math.max(dp[i - 1][1][2], dp[i - 1][0][1] - prices[i]);//未操作，或者今天买，第二次买
        }
        int last = prices.length - 1;
    		// 最后一天肯定是要卖出的，这恐怕是常识。
        return Math.max(Math.max(dp[last][0][0], dp[last][0][1]), dp[last][0][2]);
    }
}
// NOTE 1: -10001是我设定的非法值，因为在题中当天price范围未0 <= prices[i] <= 10e5
// NOTE 2: 这边也只涉及当天与前一天的计算，所以也可以用两组变量进行替换节约空间。

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析

得，就把之前的次数限制换成循环，分别进行处理罢了

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length==0 || k==0)return 0;
        k++;
        int[][][] dp = new int[prices.length][2][k];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < k; j++) {
                dp[0][i][j] = -10001;
            }
        }
        dp[0][0][0] = 0;
        dp[0][1][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0][0] = dp[i - 1][0][0];// 从来都未操作过
            // 卖出，相对于前一天：未操作  ||  今天卖
            for (int j = 1; j < k; j++) {
                dp[i][0][j] = Math.max(dp[i - 1][0][j], dp[i - 1][1][j] + prices[i]);
            }
      		  // 非法且无用的存在
            dp[i][1][0] = -10001;
            // 买入,相对于前一天：未操作  ||  今天买
            for (int j = 1; j < k; j++) {
                dp[i][1][j] = Math.max(dp[i - 1][1][j], dp[i - 1][0][j - 1] - prices[i]);
            }
        }
        int max = 0;
        int lstIdx = prices.length - 1;
        // 来个最大值
        for (int i = 0; i < k; i++) {
            max = Math.max(max, dp[lstIdx][0][i]);
        }
        return max;
    }
}

//NOTE : dp[prices.length][2][] 其中次数为0...k，也就是k+1天。