day53--动态规划12

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

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

第一题：.最佳买卖股票时机含冷冻期  

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

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

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

相比之前的股票问题，多了一个情况，卖出股票后无法在第二天买入股票，也就是说卖出后必须等待1天才能对股票进行操作。

动态规划五部曲：

（1）确定dp数组以及下标的含义

dp[i][j]，第i天的状态为j，所剩的最多现金为dp[i][j]

几个状态：

状态一：持有股票（不管是今天买入，或者昨天买入，但手上有股票）

情况二：不持有股票

        状态二：保持卖出股票的状态（两天前卖出了股票，且已经度过了一天冷冻期，）

        状态三：今天卖出股票

状态四：今天为冷冻期

状态切换：

j=0-3对应四种状态

（2）确定递推公式

达到买入股票状态（状态一）即dp[i][0] 有两个具体操作：

操作一：前一天就已经是持有状态了，dp[i][0]=dp[i-1][0]

操作二：今天买入了

        前一天是冷冻期：dp[i-1][3]-prices[i]

        前一天是保持卖出的状态，dp[i-1][1]-prices[i]

达到保持卖出股票的状态（状态二），即dp[i][1]有两种具体操作：

操作一：前一天就已经卖出了，dp[i][1]=dp[i-1][1]

操作二：前一天是冷冻期（懂了，冷冻期实际上也是另一种卖出后的情况，所以前一天是冷冻期，卖出后第三天也是卖出的状态）

dp[i][1]=max(dp[i-1][1],dp[i-1][3])

达到今天就卖出的状态（状态三），dp[i][2]，只有一个操作:

昨天一定是持有股票，今天卖出

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

达到冷冻期状态（状态四），即dp[i][3]，只有一个操作：
昨天卖出了股票：

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

综上：

dp[i][0]=max(dp[i-1][0],max(dp[i-1][3],dp[i-1][1])-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];

（3）dp数组如何初始化

对于买入股票：dp[0][0]=-prices[0]

而对于卖出股票而言：第0天都是0

（4）确定遍历顺序

dp[i][j]依赖dp[i-1][j]，所以都是从前向后遍历

（5）举例推导

第二题：买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

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

示例 1:

• 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
• 输出: 8

0、这里新加了一个条件是手续费，买进到卖出称为一次操作，需要交一次手续费，也就是说相当于卖出的时候要交一次钱。同时可以多次买进卖出，也就和前面的多次买进卖出求利润最大值一样的。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
    int n=prices.size();
    vectorint>> dp(n,vector<int>(2,0));
    dp[0][0]=-prices[0];
    for(int i=1;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 max(dp[n-1][0],dp[n-1][1]);
 
    }
};