leetcode|割冷冻韭菜的最佳时机

今天是 Kevin 的算法之路的第 16 天。为大家讲解 LeetCode 第 309 题,是昨天带来的 todo链接 的一个升级版,不了解的朋友建议先去康康。

每日一笑

“你为什么选择我们公司?”

脑子:“因为没钱啊,那你以为呢?”

嘴巴:“当然是因为你们公司balabala……”

题目描述

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]

输出: 3

解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

动态规划

了解的朋友可能知道「买股票」有一系列的题目,可以的话我会一一讲解。

这一系列的题也正涉及了重要的「动态规划」,关于动态规划可以看我今天分享的小浩算法的那篇文章。

这里先区别一下「买股票」系列中这道题的不同:

这道题增加了「冷冻期」这样一个条件,没有限制多少笔交易。因此只需要增加一个状态。

第一步:状态定义

dp[i][j] 表示[0, i]区间内,在下标为i这一天状态为j时的最大收益。

这里j取三个值:

  • 0 表示不持股;
  • 1 表示持股;
  • 2 表示处在冷冻期。

第二部:状态转移方程

这步是至关重要也是最难的,得知状态转移方程的关键是理解题意,理清逻辑。

  • 不持股可以由这两个状态转换而来:

    昨天不持股,今天什么都不操作,仍然不持股;

    昨天持股,今天卖了一股。

  • 持股可以由这两个状态转换而来:

    昨天持股,今天什么都不操作,仍然持股;

    昨天处在冷冻期,今天买了一股;

  • 处在冷冻期比较特殊,只可以由不持股转换而来,因为题目中说,刚刚把股票卖了,需要冷冻 1 天。(持股卖了变成不持股,再变成冷冻期)

以上分析可以用下图表示:

第三步:初始化(base case)

在第 0 天,不持股的初始化值为 0

持股的初始化值为 -prices[0](表示购买了一股),

虽然不处于冷冻期,但是初始化的值可以为 0

第四步:返回值

每一天都由前面几天的状态转换而来,最优值在最后一天。取不持股和冷冻期的最大者。

代码实现

//go

funcmaxProfit(prices []int)int {

length := len(prices)

// 特殊判断

if length <= 1 {

return0

}

// 声明dp

dp := make([][3]int, length)

// 初始化

dp[0][0] = 0// 【0天】【不持股】

dp[0][1] = -prices[0] // 【0天】【持股】

dp[0][2] = 0// 【0天】【冷冻期】

for i := 1; i < length; i++ {

// 【第i天】【不持股】 = max(昨天不持股今天不操作,昨天持股+今天卖一股)

dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])

// 【第i天】【持股】 = max(昨天持股今天不操作,昨天冷冻期+今天买一股)

dp[i][1] = max(dp[i-1][1], dp[i-1][2]-prices[i])

// 【第i天】【冷冻期】 = 昨天卖了不持股

dp[i][2] = dp[i-1][0]

}

// 返回不持股和冷冻期的最大者

return max(dp[length-1][0], dp[length-1][0])

}

funcmax(x, y int)int {

if x > y {

return x

}

return y

}

//java

publicclassSolution{

publicintmaxProfit(int[] prices){

int len = prices.length;

// 特判

if (len < 2) {

return0;

}

int[][] dp = newint[len][3];

// 初始化

dp[0][0] = 0;

dp[0][1] = -prices[0];

dp[0][2] = 0;

for (int i = 1; i < len; i++) {

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i]);

dp[i][2] = dp[i - 1][0];

}

return Math.max(dp[len - 1][0], dp[len - 1][2]);

}

}

郑重声明:

所展示代码已通过 LeetCode 运行通过,请放心食用~

在唠唠嗑

很多人都想养成好习惯,但大多数人却是三分钟热度。为了我们能一起坚持下去,决定制定如下计划(福利)

一起学算法,打卡领红包!

参与方式:

关注我的微信公众号「Kevin的学堂」

还可「」与众多小伙伴

一起坚持,一起学习,一起更优秀!

打卡规则为:

「留言」“打卡XXX天” ➕「分享」到朋友圈

奖励:

连续打卡 21 天,联系本人获取 6.6 元红包一个!

连续打卡 52 天,联系本人获取 16.6 元红包一个!

连续打卡 100 天,联系本人获取 66.6 元红包一个!

本文使用 mdnice 排版

以上是 leetcode|割冷冻韭菜的最佳时机 的全部内容, 来源链接: utcz.com/a/34492.html

回到顶部