免费永久vps服务器,深圳龙岗区优化防控措施,烟台做网站的价格,查询注册公司信息在哪里查309.最佳买卖股票时机含冷冻期 完成 思路#xff1a;
加入冷冻期以后#xff0c;两个状态就不够用了。
状态一#xff1a;持有股票状态#xff08;今天买入股票#xff0c;或者是之前就买入了股票然后没有操作#xff0c;一直持有#xff09;不持有股票状态#xff0…309.最佳买卖股票时机含冷冻期 完成 思路
加入冷冻期以后两个状态就不够用了。
状态一持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有不持有股票状态这里就有两种卖出股票状态 状态二保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作状态三今天卖出股票 状态四今天为冷冻期状态但冷冻期状态不可持续只有一天
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];代码
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();if (n 0) return 0;vectorvectorint dp(n, vectorint(4, 0));dp[0][0] - prices[0]; // 持股票for (int i 1; i n; i) {dp[i][0] max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], 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];}return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));}
};class Solution {public int maxProfit(int[] prices) {// dp[i][0]代表持有第i天股票收益// dp[i][1]代表不持有第i天股票收益int[][] dp new int[prices.length1][2];dp[1][0] -prices[0];dp[1][1] 0;for (int i 2; i prices.length; i) {dp[i][0] Math.max(dp[i-1][0], dp[i-2][1] - prices[i-1]);dp[i][1] Math.max(dp[i-1][1], dp[i-1][0] prices[i-1]);}return Math.max(dp[prices.length][0], dp[prices.length][1]);}
}714.买卖股票的最佳时机含手续费 完成 思路
本题的关键在于确定交手续费的时机可以买入时交也可以卖出时交关键要统一。
代码
class Solution {public int maxProfit(int[] prices, int fee) {// dp[i][0] 持有i股所得最大收益// dp[i][1] 不持有i股所得最大收益int[][] dp new int[prices.length][2];dp[0][0] -prices[0] - fee;for (int i 1; i prices.length; i) {// i-1天不持有需要买入i股并且付手续费dp[i][0] Math.max(dp[i-1][0], dp[i-1][1]-fee-prices[i]);// i-1天持有卖出i股dp[i][1] Math.max(dp[i-1][1], dp[i-1][0]prices[i]);}return Math.max(dp[prices.length-1][0], dp[prices.length-1][1]);}
}总结
121.买卖股票的最佳时机122.买卖股票的最佳时机II123.买卖股票的最佳时机III188.买卖股票的最佳时机IV309.最佳买卖股票时机含冷冻期714.买卖股票的最佳时机含手续费
首先要分清楚买入和持有的不同买入是动作不可延续持有是状态可延续。
买卖股票问题在dp数组的定义上有其特殊性由于每天的股票都有持有和不持有两种状态把dp数组定义成二维数组更好理解。其实一维数组也能解题 (比如背包问题的物品也有放和不放两个动作) 但理解上比较困难。(可能是动作和状态的区别)
