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代表前一天）
| 1 2 3 4 | sold[i]=hold[i-1]+price[i]; hold[i]=max(hold[i-1],rest[i-1]-price[i]); rest[i]=max(rest[i-1],sold[i-1]); |
那么对于最后一天来说，最大值存在两种情况：什么都不做；卖出股票。所以为max(sold,rest)。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 | int maxProfit(vector<int>& prices) { int sold=0,hold=INT_MIN,rest=0; for(int price:prices){ int pre_sold=sold; sold=hold+price; hold=max(hold,rest-price); rest=max(rest,pre_sold); } return 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为区间长度，则
| 1 2 3 4 5 6 7 8 9 10 11 | for(c in [1,N]){ for(i in [1,N-c+1])//区间起始点在[1,N-c+1]这个区间里面 { j=i+c-1;//区间长度为c-1，即代表分别计算1,2,...,N的长度区间 for(k in [i,j]){ dp[i][j]=max(num[i-1]*num[k]*num[j+1])+dp[i][k-1]+dp[k+1][j]); //当前戳中的值+其左侧戳中的值+其右侧戳中的值 } } } |
解析参考自：
https://leetcode-cn.com/problems/burst-balloons/solution/san-chong-jie-fa-by-jason-2-6/
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | int maxCoins(vector<int>& nums) { int N; N = nums.size(); nums.insert(nums.begin(), 1); nums.push_back(1);//在开头和结尾插入1，因为题目说-1和最后一个位置当做1 const int len = nums.size(); vector<vector<int>> dp(len, vector<int>(len, 0)); for (int i = 1; i <= N; ++i) { for (int j = 1; j + i - 1 <= N; ++j) { const int k = j + i - 1; int& ans = dp[j][k]; for (int m = j; m <= k; ++m) { ans = max(ans, nums[j - 1] * nums[m] * nums[k + 1] + dp[j][m - 1] + dp[m + 1][k]); } } } return dp[1][N]; } |
复杂度分析
