韶关市住房和城乡建设部网站,wordpress+极简博客,wordpress memcached命中率,合肥做推拉棚网站推广1.最佳买卖股票时机含冷冻期
309. 最佳买卖股票时机含冷冻期 1.dp数组的含义#xff1a;dp[i][0]为第i天卖出股票的最大价值#xff1b;dp[i][1]为第i天持有股票的最大价值 2.dp数组的条件#xff1a;由于有冷冻期#xff0c;所以dp数组的条件就变了。第i天卖出股票的最大…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(vectorint prices) {if(prices.size()1)return 0;vectorvectorintdp(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 i2;iprices.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(vectorint prices, int fee) {vectorvectorintdp(prices.size(),{0,0});dp[0][0]0;dp[0][1]-prices[0];for(int i1;iprices.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数组对应操作规范最后还需要观察是否需要特殊的初始化。
