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

—

by

FeanLau
in ,
目录
show

一、穷举框架

思路一层 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]);
    }
}