309.买卖股票的最佳时机含冷冻期
题目描述:
给定一个整数数组prices
,其中第 prices[i]
表示第 *i*
天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
数据范围:
1≤prices.len≤5×1031≤prices.len≤5×103
题解:
状态为:持有,卖出(不持有,不在冷冻期),不持有(处于冷冻期)。处于冷冻期说明前一天进行了卖出操作。
使用 dp[i][j]dp[i][j] 表示第 ii 天处于状态 jj 时的利润。
当处于第 ii 天时,如果处于持有状态,说明前一天就持有,或者是前一天处于(不持有,不在冷冻期),这一天进行了买入操作。即 dp[i][0]=max(dp[i−1][0],dp[i−1][1]−prices[i])dp[i][0]=max(dp[i−1][0],dp[i−1][1]−prices[i]) ;
如果处于不持有且不在冷冻期状态,说明前一天就处于该状态,或者前一天处于冷冻期。即 dp[i][1]=max(dp[i−1][1],dp[i−1][2])dp[i][1]=max(dp[i−1][1],dp[i−1][2]) ;
如果处于不持有且在冷冻期状态,说明前一天进行了卖出操作,前一天持有。即 dp[i][2]=dp[i−1][0]+prices[i]dp[i][2]=dp[i−1][0]+prices[i] .
注意初始条件,当处于第 00 天时, dp[0][0]=−prices[i],dp[0][1]=0,dp[0][2]=0dp[0][0]=−prices[i],dp[0][1]=0,dp[0][2]=0 ,其中 dp[0][2]dp[0][2] 没有这个状态,但是为了 dp[1]dp[1] 将其设置为了 00 。
也可以只用持有和不持有两个状态,从 i=2i=2 开始遍历,这样更容易理解。
dp[i][0]=max(dp[i−1][0],dp[i−2][1]−prices[i])dp[i][1]=max(dp[i−1][1],dp[i−1][0]+prices[i])dp[i][0]=max(dp[i−1][0],dp[i−2][1]−prices[i])dp[i][1]=max(dp[i−1][1],dp[i−1][0]+prices[i])初始条件 dp[0][0]=−prices[0],dp[0][1]=0; dp[1][0]=max(dp[0][0],−prices[1]),dp[1][1]=max(0,prices[1]−prices[0])
代码:
1 | auto optimize_cpp_stdio = []() |
v1.5.1