力扣股票问题（买卖股票的最佳时机）代码及思路合集 动态规划

1. 本篇展示的是代码和思路注释。
2. 解题方法全部使用的动态规划
3. 代码使用的是java语言
4. 由于题目较多，并未将题目详细要求展示出来，但每个题目都附带超链接，需要看题目的话可以点击跳转。
5. 使用的是dp的原始版本，有的题目AC之后显示的时间的空间可能会吓一跳，这很正常，力扣的时空评判有相对性和随机性，思路肯定是没有问题的。大家可以自行空间优化，一般将[i-1]去掉即可。

class Solution {
    public int maxProfit(int[] prices) {    //dp
    	//dp[i][0]表示第i天是【持有股票状态】的最大利润，dp[i][1]表示第i天是【不持有股票状态】的最大利润
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];  //第0天是持有状态的话只能是买入
        dp[0][1] = 0;   //第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];//返回最后一天非持有状态
    }
}

class Solution {
    public int maxProfit(int[] prices) {    //dp；注意当天卖了再买和当天买了再卖是没有意义的
        if(prices.length == 1) return 0;
        //dp[i][0]表示当前是【持有状态】；dp[i][1]表示当前是非持有状态
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < prices.length; i++) {
            //不是第i天买入的/是第i天买入的
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            //不是第i天卖出的/是第i天卖出的
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];
    }
}

class Solution {
    //dp;0：未持过股状态，1：第一次已买入状态，2：第一次已卖出状态，3：第二次已买入状态，4：第二次已卖出状态
    public int maxProfit(int[] prices) {
        if(prices.length == 1) return 0;
        //dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j的最大利润。
        int[][] dp = new int[prices.length][5];
        //dp[0][0]，dp[0][2]，dp[0][4]都是0，所以取默认值即可
        dp[0][1] = -prices[0];  //买入
        dp[0][3] = -prices[0];  //相当于同一天买入了之后又卖出，然后又买入
        for(int i = 1; i < prices.length; i++) {    //遍历不同的日子；注意未持过股状态必然是0
            //每个状态要么是前一天的相同状态，要么是由前一天的前一个状态推导来的
            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]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.length - 1][4];
    }
}

class Solution {
 //dp；0：未持过股状态，奇数：第k次已买入状态，偶数：第k次已卖出状态（不一定是当天卖的）
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if(len == 0) return 0;
        //dp[i][j]表示第i天j状态，所剩下的最大现金（截止第i天所获得的利润）
        int[][] dp = new int[len][2 * k + 1];
        for(int i = 1; i < 2 * k + 1; i += 2) {
            dp[0][i] = -prices[0];
        }
        for(int i = 1; i < len; i++) {  //0已初始化，故从1开始，遍历不同的日子
            for(int j = 1; j < 2 * k + 1; j += 2) { //未持过股状态默认为0即可
                //每个状态要么是前一天的相同状态，要么是由前一天的前一个状态推导来的
                //奇数状态表示买入状态，两种情况：非今天买入/今天买入（前一天就应该为j-1状态）
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                //偶数状态j+1表示卖出状态，两种情况：非今天卖出/今天卖出（前一天就应该为j状态）
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }
        return dp[len - 1][2 * k];
    }
}

class Solution {
    //dp；0：持有股票状态，1：冷冻期之后非持有股票的状态，2：今天卖出了股票，3：今天是冷冻期
    public int maxProfit(int[] prices) {    //1,2,3都是属于非持有状态
        int len = prices.length;
        if(len == 1) return 0;
        int[][] dp = new int[len][4];	//dp[i][*]表示从开始到第i天的在*状态下的累计收益
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; i++) {
            //昨天就是0状态/昨天是1状态/昨天是冷冻期
            dp[i][0] = Math.max(dp[i - 1][0], 
            		Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);//昨天就是1状态/昨天是冷冻期
            dp[i][2] = dp[i - 1][0] + prices[i];    //昨天为持有状态
            dp[i][3] = dp[i - 1][2];
        }
        //最后在3个非持有状态里选一个
        return Math.max(Math.max(dp[len - 1][1], dp[len - 1][2]), dp[len - 1][3]);
    }
}

class Solution {
    public int maxProfit(int[] prices, int fee) {   //dp；0：持有状态，1：非持有状态
        int len = prices.length;
        int[][] dp = new int[len][2];   //dp[i][*]表示从开始到第i天的在*状态下的累计收益
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; 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] - fee);
        }
        return dp[len - 1][1];
    }
}