【代码随想录】刷题Day51

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

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

1.dp数组的含义：dp[i][0]为第i天卖出股票的最大价值；dp[i][1]为第i天持有股票的最大价值

2.dp数组的条件：由于有冷冻期，所以dp数组的条件就变了。第i天卖出股票的最大价值有两种情况，一是上一次卖出股票的最大价值，二是前一次持有股票现在卖出的最大价值，那么条件就是dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])。第i天持有股票的最大价值也有两种，一为上一次持有股票的最大价值，二为两天前卖出股票的最大价值(因为冷冻期不能卖上一天持有的股票)，那么条件为dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i]);

3.初始化：dp[0][0]=0和dp[0][1]=-prices[0]没什么好说的。但是由于我们的持股逻辑变为i-2，也就是说如果从1开始遍历会出现越界访问，那么我们需要提前设置1位置的值，1位置的逻辑是不需要考虑冷冻期的，所以延续前几题对dp数组条件的理解，自然知道初始化为：dp[1][0]=max(dp[0][0],dp[0][1]+prices[1])和dp[1][1]=max(dp[0][1],dp[0][0]-prices[1]);

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

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

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

与122. 买卖股票的最佳时机 II相似

犹豫本题加入了所谓的“手续费”，因此其实条件需要在卖出股票的时候需要将手续费一并减去，说白了就是在原来卖出的基础上便宜了一点，但是我们寻找卖出的最大价值随着dp数组的含义不变而不变。数组的含义依然是最大值，只不过可能频繁交易会出现原先频繁买卖的股票方法可能小了，但是dp数组依然是通过每一次的买入卖出得到包含减去手续费的最有价值的方法，那么条件自然只需要减去fee即可，所以变成了dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)

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

3.总结

我是觉得股票类问题核心就是在确定d数组到底表示一些什么，应该这么定义能把所有的情况囊括进去。

1.比如最开始的股票问题，只是找最大值，那么我们就不需要考虑需要累加的问题，直接取最大值比较。

2.比如后面的累加最大价值，那么其实就是将上一次的价值和当前卖出的股票价值加上求出最大值，比起最开始的求一次最大值也就多了一步处理逻辑。

3.又限制购买次数，这样我们所设定的dp数组又需要表示第n次持股或者抛股的定义。最后根据上下关系进行条件判断

那么其实都是需要先清楚题目条件，找到适合的dp数组定义，是否多次或者一次的买入。随后看给出的条件对dp数组条件进行模拟，其实模拟的思路很简单，针对单个条件就是看前一次和当前次的关系；针对整体，则是看每层相互的关系。当确定条件后，根据条件进行对应的初始化。初始化最开始的值要满足题目描述和dp定义以及dp数组对应操作规范，最后还需要观察是否需要特殊的初始化。