【算法】【动态规划】买股票的最佳时机

深藏阁楼爱情的钟 2024-04-05 07:21 96阅读 0赞

## 121 ##

*  [买卖股票的最佳时机 - 买卖股票的最佳时机 - 力扣（LeetCode）][- _ - _LeetCode]

//版本一
    class Solution1 {
          
        /**  
         * 分析：  
         * 取两个数，求第二个数减第一个数最大值  
         * 条件是如果这个差是负数，则返回0  
         *     * @param prices  
         * @return  
         */  
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int[][] dp = new int[n][2];//dp[i][0]表示第i天持有股票，dp[i][1]表示第i天不持有股票  
            dp[0][0] = -prices[0];  
            dp[0][1] = 0;  
            for (int i = 1; i < n; 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[n - 1][1];  
        }  
    }
    
    //版本二
    class Solution {
          
        /**  
         * 优化空间，使用滚动数组  
         *  
         * @param prices  
         * @return  
         */  
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int []dp=new int[2];//0 持有股票，1 不持有股票  
            dp[0]=-prices[0];  
            dp[1]=0;  
            for (int i = 1; i < n; i++) {
          
                dp[0]=Math.max(dp[0],-prices[i]);  
    			dp[1]=Math.max(dp[1],dp[0]+prices[i]);
    			
    
    	
            }  
            return dp[1];  
        }  
    }

## 122 ##

*  [122. 买卖股票的最佳时机 II - 力扣（LeetCode）][122. _ II - _LeetCode]

相对121的变化是  
交易次数从1变为没有限制

//版本一
    class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n = prices.length;  
            int[][] dp = new int[n][2];     // 创建二维数组存储状态  
            dp[0][1] = 0;                   // 初始状态  
            dp[0][0] = -prices[0];  
            for (int i = 1; i < n; ++i) {
          
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);    // 第 i 天，没有股票  
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);    // 第 i 天，持有股票  
            }  
            return dp[n - 1][1];    // 卖出股票收益高于持有股票收益，因此取[0]  
        }  
    }
    
    //版本二
    class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int []dp=new int[2];//0 表示持仓，1 表示空仓  
            dp[0]=-prices[0];  
            dp[1]=0;  
            for (int i = 1; i < n; i++) {
          
                dp[0]=Math.max(dp[0],dp[1]-prices[i]);  
    			dp[1]=Math.max(dp[1],dp[0]+prices[i]); 
    			/**  
    			if(dp[0]>dp[1]-prices[i]){  
    			    //dp[0]=dp[0];    
    			    dp[1]=Math.max(dp[1],dp[0]+prices[i]);    
    			}else{  
    				dp[0]=dp[1]-prices[i];   
                    //dp[1]=Math.max(dp[1],dp[0]+prices[i]); 即dp[1]=dp[1];  
    			}  
    			但是309题不能直接替换，需要加入temp值
    			 */
            }  
            return dp[1];  
        }  
    }

## 123 ##

*  [123. 买卖股票的最佳时机 III - 力扣（LeetCode）][123. _ III - _LeetCode]

相比121的变化是  
交易次数限制为2

class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int [][]dp=new int[n][4];  
            /**  
             * 0表示第一次交易机会持仓  
             * 1表示第一交易机会空仓  
             * 2表示第二次交易机会持仓  
             * 3表示第二次交易机会空仓  
             */  
            dp[0][0]=-prices[0];  
            dp[0][1]=0;  
            dp[0][2]=-prices[0];  
            dp[0][3]=0;  
            for (int i = 1; i < n; 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[n-1][3];  
        }  
    }
    //版本二
    class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int []dp=new int[4];  
            /**  
             * 0表示第一次交易机会持仓  
             * 1表示第一交易机会空仓  
             * 2表示第二次交易机会持仓  
             * 3表示第二次交易机会空仓  
             */  
            dp[0]=-prices[0];  
            dp[1]=0;  
            dp[2]=-prices[0];  
            dp[3]=0;  
            for (int i = 1; i < n; i++) {
          
                dp[0]=Math.max(dp[0],-prices[i]);  
                dp[1]=Math.max(dp[1],dp[0]+prices[i]);  
                dp[2]=Math.max(dp[2],dp[1]-prices[i]);  
                dp[3]=Math.max(dp[3],dp[2]+prices[i]);  
            }  
            return dp[3];  
        }  
    }

## 188 ##

*  [188. 买卖股票的最佳时机 IV - 力扣（LeetCode）][188. _ IV - _LeetCode]

//版本一
    class Solution {
          
        public int maxProfit(int k, int[] prices) {
          
            int n=prices.length;  
            if(n==0) return 0;  
            int [][]dp=new int[n][2*k+1];//偶数代表持仓，奇数代表空仓  
            for (int i = 1; i < 2 * k+1; i+=2) {
          
                dp[0][i]=-prices[0];  
                dp[0][i+1]=0;  
            }  
            for (int i = 1; i < n; i++) {
          
                for (int j = 1; j < 2 * k+1; j+=2) {
          
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);  
                    dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]+prices[i]);  
                }  
            }  
            return dp[n-1][2*k];  
        }  
    }
    //版本二
    class Solution {
          
            public int maxProfit(int k, int[] prices) {
          
                int n=prices.length;  
                if(n==0) return 0;  
                int []dp=new int[2*k+1];//偶数代表持仓，奇数代表空仓  
                for (int i = 1; i < 2 * k+1; i+=2) {
          
                    dp[i]=-prices[0];  
                    dp[i+1]=0;  
                }  
                for (int i = 1; i < n; i++) {
          
                    for (int j = 1; j < 2 * k+1; j+=2) {
          
                        dp[j]=Math.max(dp[j],dp[j-1]-prices[i]);  
                        dp[j+1]=Math.max(dp[j+1],dp[j]+prices[i]);  
                    }  
                }  
                return dp[2*k];  
            }
    }

## 309 ##

*  [309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）][309. _ - _LeetCode]

class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int [][]dp=new int[n][3];  
            /**  
             * 0 代表持仓  
             * 1 代表空仓，卖出股票的结果  
             * 2 代表空仓，延续之前空仓的结果  
             */  
            dp[0][0]=-prices[0];  
            dp[0][1]=0;  
            dp[0][2]=0;  
            for (int i = 1; i < n; i++) {
          
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);//买入股票的继承状态是从前一天的延续空仓得来  
                dp[i][1]=dp[i-1][0]+prices[i];  
                dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);//延续空仓，是延续前一天的空仓，无论前一天的空仓是如何形成的  
            }  
            return Math.max(dp[n-1][1],dp[n-1][2]);  
        }  
    }
    
    //版本二
    class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int []dp=new int[3];  
            /**  
             * 0 代表持仓  
             * 1 代表空仓，卖出股票的结果  
             * 2 代表空仓，延续之前空仓的结果  
             */  
            dp[0]=-prices[0];  
            dp[1]=0;  
            dp[2]=0;  
            for (int i = 1; i < n; i++) {
          
                int dp0=Math.max(dp[0],dp[2]-prices[i]);//买入股票的继承状态是从前一天的延续空仓得来  
                int dp1=dp[0]+prices[i];  
                int dp2=Math.max(dp[1],dp[2]);//延续空仓，是延续前一天的空仓，无论前一天的空仓是如何形成的  
                dp[0]=dp0;  
                dp[1]=dp1;  
                dp[2]=dp2;  
            }  
            return Math.max(dp[1],dp[2]);  
        }
    }
    //版本三
    class Solution {
          
        public int maxProfit(int[] prices) {
          
            int n=prices.length;  
            int[][] dp = new int[n + 1][2];  
            dp[1][0] = -prices[0];  
            dp[1][1]=0;  
      
            for (int i = 2; i < dp.length; i++) {
          
                /*  
                dp[i][0] 第i天持有股票收益;  
                dp[i][1] 第i天不持有股票收益;  
                情况一：第i天是冷静期，不能以dp[i-1][1]购买股票,所以以dp[i - 2][1]买股票，没问题  
                情况二：第i天不是冷静期，理论上应该以dp[i-1][1]购买股票，但是第i天不是冷静期说明，第i-1天没有卖出股票，  
                    则dp[i-1][1]=dp[i-2][1],所以可以用dp[i-2][1]买股票，没问题  
                 */           
    			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 2][1] - prices[i - 1]);  
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1]);  
            }  
      
            return dp[n][1];  
        }
    }

## 714 ##

*  [714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）][714. _ - _LeetCode]

class Solution {
          
        public int maxProfit(int[] prices, int fee) {
          
            int n=prices.length;  
            int [][]dp=new int[n][2];//0 代表持有，1 代表不持有  
            dp[0][0]=-prices[0];  
            dp[0][1]=0;  
            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-1][1];  
      
      
        }  
    }
    //版本二
    class Solution {
          
        public int maxProfit(int[] prices, int fee) {
          
            int n=prices.length;  
            int []dp=new int[2];//0 代表持有，1 代表不持有  
            dp[0]=-prices[0];  
            dp[1]=0;  
            for (int i = 1; i < n; i++) {
          
    	        dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);  
    			dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee);
    			
     
            }  
            return dp[1];  
      
      
        }
        
    }

[- _ - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
[122. _ II - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[123. _ III - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
[188. _ IV - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
[309. _ - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[714. _ - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/