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

这道题算是股票问题的变体之一，主要在于不限制交易次数而存在冷冻期，所以我们需要对我们的dp数组进行改变，第一维是指第几天，第二维是指是否持有股票，在这里因为不限制交易次数k，所以并未涉及第三维度。

同时，在这里我的状态转移方程为：

第i天未持有股票的可能性有：1.第i-1天未持有股票 2.第i-1天持有股票后卖出了。

 dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);

第i天持有股票的可能性有：1.第i-1天持有股票 2.第i-1天未持有股票，且非冷冻期买入。此时第二种情况为dp[i-2][0]-prices[i-1],原因在于：由上一个方程可知，dp[i-1][0]=Math.max(dp[i-2][0],dp[i-2][1]+prices[i-2]);我们需要的是非冷冻期的买入，所以取dp[i-2][0].

不妨设想，冷冻期如果不是两天，而是k天，我们也可以直接取为dp[i-k][0];

 dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i-1]);

    public int maxProfit(int[] prices) {

        int [][] dp=new int[prices.length+1][3];

        dp[0][0]=dp[1][0]=0;

        dp[0][1]=Integer.MIN_VALUE;

        dp[1][1]=-prices[0];

        for(int i=2;i<=prices.length;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-2][0]-prices[i-1]);

            }

            return dp[prices.length][0];

    }

巴特西

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

最新文章

热门文章