leetcode动态规划（买卖股票问题）

怼烎@ 2022-09-05 15:51 211阅读 0赞

1.  买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。

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

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。  
输入：\[7,1,5,3,6,4\]  
输出：5  
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。  
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

假设在第n天出售，则第n天的最大获利为n天之前的最小值购入，在第n天卖出，这样获利最大。

class Solution {
        
        public int maxProfit(int[] prices) {
        
        int l=prices.length;
        int[] dp=new int[l];
        int[] mi=new int[l];
        mi[0]=prices[0];
        dp[0]=0;
        int ma=0;
        for(int i=1;i<l;i++){
        
        mi[i]=Math.min(mi[i-1],prices[i-1]);//计算第n天之前的最小值
        dp[i]=prices[i]-mi[i];//计算利润
        ma=Math.max(dp[i],ma);
        }
        return ma;
        }
    }

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

给定一个数组 prices ，其中 prices\[i\] 是一支给定股票第 i 天的价格。

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

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

输入: prices = \[7,1,5,3,6,4\]  
输出: 7  
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

与上一题的的区别是，可以进行多次交易，动态规划的核心是状态划分。  
第一维：时间，第n天。  
第二维：状态，是否持有股票（0，1）。  
0表示无股票，则第i天无股票的最大利润为：  
1.dp\[i-1\] \[0\]前一天也没有股票，与上一天相等。  
2.dp\[i-1\] \[1\]+price\[i\]，前一天有，这天卖掉了，加上今天的价格的收益。  
1表示有股票，同上有两种状态。

class Solution {
        
        public int maxProfit(int[] prices) {
        
        int n=prices.length;
        int[][] dp=new int[n][2];//0代表当前没有股票，1代表有
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++){
        
            dp[i][0]=Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
        }
    }

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

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

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

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

此题最多完成两次交易，首先进行状态划分。  
1.有票，没卖过  
2.无票，卖过一次  
3.有票，卖过一次  
4.无票，卖国两次

class Solution {
        
        public int maxProfit(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;
        }
    }

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

给定一个整数数组 prices ，它的第 i 个元素 prices\[i\] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。  
给定参数k来限制交易次数。  
则状态划分为三维分别是，第n天，是否持有股票，已经交易了i次。  
注意对边界值的处理，第一天不可能交易1次及以上，都初始化为无穷小。  
交易次数以卖出为统计标准。  
第i天持有股票，要么是与上一天一样即dp\[i-1\]\[1\]\[x\];要么是上一天买入了股票，dp\[i - 1\]\[0\]\[x\] - prices\[i\]  
若第i天无股票，要么与上一天一致，为dp\[i-1\]\[0\]\[x\];要么是上一天卖出了股票，dp\[i - 1\]\[1\]\[x - 1\] + prices\[i\]

class Solution {
        
        public int maxProfit(int k, int[] prices) {
        
            // 状态定义：dp[i][j][k]表示第i天持有或不持有股票在交易K次的情况下的最大利润，其中j取值0表示不持有，1表示持有
            // 状态转移：1、如果第i天持有股票，这个股票有可能是前一天就持有的，这时候：dp[i][1][k]=dp[i-1][1][k]
            //          2、如果第i天持有股票，这个股票有可能是当天新买入的，这时候：dp[i][1][k]=dp[i-1][0][k] - prices[i]
            //          3、如果第i天不持有股票，可能是前一天就不持有股票，这时候：dp[i][0][k]=dp[i-1][0][k]
            //          4、如果第i天不持有股票，可能是当天卖出了股票，这时候：dp[i][0][k]=dp[i-1][1][k-1] + prices[i]
            // 所以，以上四种情况可以合成两种，即当天持有和不持有交易K次的最大收益
            int n = prices.length;
            if (n < 2) {
        
                return 0;
            }
    
            int[][][] dp = new int[n][2][k + 1];
            // 初始值，第0天持有，即买入
            dp[0][1][0] = -prices[0];
            // 初始值，第0天，不持有，即不操作
            dp[0][0][0] = 0;
    
            int inf = Integer.MIN_VALUE / 2;
            // 使用x表示k的下标
            for (int x = 1; x <= k; x++) {
        
                // 第一天不可能交易1次及以上
                dp[0][0][x] = dp[0][1][x] = inf;
            }
    
            for (int i = 1; i < n; i++) {
        
                for (int x = 0; x <= k; x++) {
        
                    // 第i天持有股票且交易x次，持有的股票可能来自前一天，也可能是当天买入的
                    dp[i][1][x] = Math.max(dp[i - 1][1][x], dp[i - 1][0][x] - prices[i]);
                    // 第i天不持有股票且交易x次，原因可能是前一天就不持有，也可能当天卖出了
                    dp[i][0][x] = Math.max(dp[i - 1][0][x], x == 0 ? inf : dp[i - 1][1][x - 1] + prices[i]);
                }
            }
    
            // 输出结果
            //return dp[n-1][0][k]
            return IntStream.of(dp[n - 1][0]).max().getAsInt();
        }
    }

不能返回return dp\[n-1\]\[0\]\[k\]，因为最大值不一定交易了k次，但一定是最后一天，并且不持有股票的，所以在这二维确定的条件下搜索最大值返回。

1.  最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

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

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

class Solution {
        
        public int maxProfit(int[] prices) {
        
        int n=prices.length;
        int[][] dp=new int[n][2];//0代表当前没有股票，1代表有
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++){
        
            dp[i][0]=Math.max(dp[i-1][1]+prices[i],dp[i-1][0]);
            if(i>1){
        
            dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]);}//这里是-2。
            else{
        
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            }
        }
        return dp[n-1][0];
        }
    }