Leetcode 309:最佳买卖股票时机含冷冻期

题目描述

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

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

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例

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

解题思路

这又是一个动态规划问题,我们思考该题的状态图。一共可能有三个状态:

  • Hold:购入股票;
  • Sold:卖出股票;
  • Rest:持有股票什么都不做。

那么如何能得到这三个状态呢?

对于Hold来说:

  • 前一天持有,当日Rest;
  • 前一天Rest,当日买入股票。

对于Sold来说:

  • 前一日Hold股票,当日卖出。

对于Rest来说:

  • 前一日Sold了,当日必须Rest;
  • 也可以前一天Rest,当日继续Rest。

所以说状态转换图如下:

复杂度配图

由上面的状态转换图我们可以得到:
(以下i表示第i天,i-1代表前一天)

那么对于最后一天来说,最大值存在两种情况:什么都不做;卖出股票。所以为max(sold,rest)

代码实现

复杂度分析

时间复杂度:O(n)

复杂度配图

LeetCode 312:戳气球

题目描述

n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例

输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
  coins = 315 + 358 + 138 + 181 = 167

解题思路

这个题类似于游艇租赁问题,游艇租赁问题就是找分隔点,而本题也是类似的。这种动态规划问题和我们前面遇到的是不太一样的。

动态规划问题就是将一个大问题分隔成多个独立的小问题。在这个问题上,就是我们可以将大的区间分隔为独立的小区间,然后先戳爆小区间,也就是先算小区间,再组合出大区间。

对于本题的示例[3,1,5,8]来说,步骤如下:

第一步:计算长度为1的区间,分别戳3,1,5,8。

第二步:计算长度为2的区间,分别算[3,1],[1,5],[5,8]:
对于3,1:3最后戳,1已经算出;同样1最后戳,3也算出;
对于1,5:1最后戳,5已经算出;同样5最后戳,1也算出;
对于5,8:5最后戳,8已经算出;同样8最后戳,5也算出。

第三步,计算长度为3的区间,分别计算[3,1,5]和[1,5,8]:
对于3,1,5来说,3最后戳,1/5已经计算出来;1最后戳,3/5已经计算出来;5最后戳,3,1已经计算出来;
对于1,5,8来说,1最后戳,5/8已经计算出来;5最后戳,1/8已经计算出来;8最后戳,1,5已经计算出来。

第四步,计算长度为4的区间,即[3,1,5,8]:3最后戳,1,5,8已经算出。1最后戳3和5,8已经算出。5最后戳,3,1和8已经算出。8最后戳,3,1,5已经算出。

简单来说,写一个伪代码:
序列为num[i,j]为区间,dp[i][j]为dp数组;c为区间长度,则

解析参考自:
https://leetcode-cn.com/problems/burst-balloons/solution/san-chong-jie-fa-by-jason-2-6/

代码实现

复杂度分析

复杂度配图