1. question: 最佳买卖股票时机含冷冻期(中等)
给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
示例 1:
1 | 输入: prices = [1,2,3,0,2] |
示例 2:
1 | 输入: prices = [1] |
提示:
1 | 1 <= prices.length <= 5000 |
2. answers
这道题多了一个冷冻期,整体上和多次交易大同小异,只不过不持有股票拆分成了两个状态:不持有股票【允许交易】和冷冻期。即每一天有三个状态:
- 持有股票:
dp[i][0]
,可由以下状态得到:- dp[i-1][0]:保持前一天买入的股票
- dp[i-1][2] - prices[i]:冷冻期过后,买入股票
- 不持有股票:
dp[i][1]
,可由以下状态得到:- dp[i-1][1]:保持前一天的状态
- dp[i-1][0] + prices[i]:本天卖出
- dp[i-1][2]:即冷冻期过后就可以买卖了,此时仍然不买入如票
- 冷冻期:
dp[i][2]
,可由以下状态得到:- dp[i-1][1]:前一天卖出
代码如下所示:
1 | public class Solution_0135 { |
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。