动态规划--买卖股票含冷冻期309-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划--买卖股票含冷冻期309。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划--买卖股票含冷冻期309,算法,动态规划,算法

这道题很明显下一天的利润需要由上一天的状态推导出来，所以这是很明显的动态规划问题

普通的股票问题有两种状态：持有股票的利润，不持有股票的利润，但这道题有一个冷冻期，使得这道题有4种状态：

1、持有股票的利润； j==0

不持有股票（持有--》不持有）利润：

2、继承上一次所有不持有导致的不持有股票（下次没有冷冻期）利润状态 j==1

3、上一次没有卖出股票所导致的不持有股票（下次有冷静期）利润状态 j==2

4、冷冻期（上次状态3）不持有股票的利润 j==3

动态五部曲：

1、定义dp数组含义：dp[i][j]第i天第j个状态所得到的利润

2、确定递推公式：

持有股票利润来源：上一次持有、上次没有卖出股票这次买入、冷冻期的不持有买入

Math.max( dp[i-1][0] , dp[i-1][1]-prices[i] , dp[i-1][3]-prices[i]） j==0

上次卖出股票，这次不持有（下次没有冷冻期）来源：上次所有不持有的状态

Math.max( dp[i-1][1] ， dp[i-1][2] , dp[i-1][3]） j==1

上次没有卖出股票，这次不持有（下次有冷静期）来源：上次持有，这次卖出

dp[i-1][0]+prices[i] j==2

冷冻期的不持有来源：上次卖出股票的不持有

dp[i-1][2] j==3

3、初始化

dp[0][0] = prices[i] ; 第一次买入股票导致利润为负,其余不持有状态初始化为0

4、遍历顺序

从前往后，因为需要前一个状态来推导下一个状态

5、打印dp数组

动态规划--买卖股票含冷冻期309,算法,动态规划,算法

代码如下：

int[][] dp = new int[prices.length][4];
        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        for(int i = 1;i<prices.length;i++){
            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][3],Math.max(dp[i-1][1],dp[i-1][2]));//保持不持有状态
            dp[i][2] = dp[i-1][0]+prices[i];//卖出股票后不持有 上次持有变不持有
            dp[i][3] = dp[i-1][2];
        }
        for(int i = 0;i<dp.length;i++){
            for(int j = 0;j<dp[0].length;j++){
                System.out.print(" "+dp[i][j]);
            }
            System.out.println();
        }
        return Math.max(dp[dp.length-1][1],Math.max(dp[dp.length-1][2],dp[dp.length-1][3]));

文章来源地址https://www.toymoban.com/news/detail-861087.html

到了这里，关于动态规划--买卖股票含冷冻期309的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！