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

原创
2019/09/13 20:02
阅读数 381

一、穷举框架

思路一层for循环 dp[][]保存每一个步骤的状态,应该是两层for循环的。

二、子问题公式

dp[i]与dp[i-1]与prices[i](当前的价格)之间的关系?这是要去思考的?

sell[i] = max ( sell[i-1] + profit, rest[i-2] + profit, 0 );
rest[i] = max ( sell[i-1], rest[i-1]);

三种状态,但是有一种状态没有必要去考虑的

代码部分:

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2) return 0;
        int n = prices.length, max;
        int[] sell = new int[n];
        int[] rest = new int[n];
        
        sell[0] = 0;
        sell[1] = Math.max(prices[1] - prices[0], 0);
        for(int i = 2; i < sell.length; i++){            
            int profit = prices[i]-prices[i-1];
            sell[i] = Math.max(Math.max( sell[i-1], rest[i-2] ) + profit, 0);
            rest[i] = Math.max(sell[i-1], rest[i-1]);
        }
        return  Math.max(sell[n-1], rest[n-1]);
    }
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部