leetcode题目解析(191029)

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代表前一天)

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)

代码实现

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为区间长度,则

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/

代码实现

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];
}

复杂度分析

复杂度配图

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注