算法练习-day40

动态规划

309. 买卖股票的最佳时机含冷冻期

题意：给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

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

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

实例：

思路：本题可以算是买卖股票2问题的延伸。我们也是可以多次买卖股票并获取最大利润，但是本题我们有四种状态：

1. 当前持有股票的全部金额
2. 当前不持有股票且冷冻期已经结束的金额
3. 当天卖出股票的金额
4. 冷冻期的金额

这四种状态，分别对应动态规划数组dp的0，1，2，3

首先是初始化，我们将持有股票的状态，即dp[0][0]设置为-prices[0]，其他的设置为0；其次是递推公式：

1. 对于第i天持有股票的状态，我们有三种选择：1.前一天的持有股票状态，2.前一天不持有股票且冻结期已过-当天买入股票，3.冻结期-当天买入股票三种情况的最大值
2. 对于第i天不持有股票的状态，我们选择前一天不持有股票状态和冻结期状态的最大值进行继承
3. 对于第i天卖出股票的情况，就一种情况，就是前一天持有股票金额+当天卖出股票金额
4. 对于第i天冻结金额，就是前一天卖出股票的金额

以上四种递推公式对于上述四种状态，最后我们输出的是后三种情况的最大值。

C++代码：

    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(4));
        dp[0][0]=-prices[0],dp[0][1]=0,dp[0][2]=0,dp[0][3]=0;
        for(int i=1;i<prices.size();i++)
        {
            dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
            dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));
    }

714. 买卖股票的最佳时机含手续费

题意：给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

实例：

思路：本题也是买卖股票2的一个简单变种，基本思路都不变。总共有两种状态：持有股票和不持有股票。这个小费问题，我们只需要在每次收钱时，在我们的利润里减去即可，代码几乎没有变化。

C++代码：

    int maxProfit(vector<int>& prices, int fee) {
        vector<vector<int>> dp(prices.size(), vector<int>(2));
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[prices.size() - 1][1];
    }