当前网站开发用什么软件,谷歌推广seo,宁波网络推广推荐,网络营销方式包括哪些目录
309.最佳买卖股票时机含冷冻期
前言
思路
算法实现 714.买卖股票的最佳时机含手续费
前言
思路 算法实现
股票问题总结 309.最佳买卖股票时机含冷冻期 题目链接 文章链接 前言 本题在买卖股票II的基础上增加了一个冷冻期#xff0c;因此就不能简单分为持有股票和卖…目录
309.最佳买卖股票时机含冷冻期
前言
思路
算法实现 714.买卖股票的最佳时机含手续费
前言
思路 算法实现
股票问题总结 309.最佳买卖股票时机含冷冻期 题目链接 文章链接 前言 本题在买卖股票II的基础上增加了一个冷冻期因此就不能简单分为持有股票和卖出股票两个状态了。
思路 利用动规五部曲进行分析
1.确定dp数组及其下标的含义 dp[i][j]第i天状态为j所剩的最多现金为dp[i][j] 本题的状态j可以分为如下四个状态
状态一持有股票状态因为冷冻期的存在由不持有股票状态引申出以下两种状态 状态二保持卖出股票的状态两天前就卖出了股票并且已经度过了冷冻期并保持未购入股票的状态 状态三今天卖出股票
状态四冷冻期
2.确定递推公式 对于状态一的前一天可能有多种情况 情况一前一天也为持有股票状态dp[i][0] dp[i - 1][0]; 情况二前一天为处于保持卖出股票的状态第i天购入股票则dp[i][0] dp[i - 1][1] - prices[i]; 情况三前一天刚好为冷冻期第i天购入股票则dp[i][0] dp[i - 1][3] - prices[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] dp[i - 1][1]; 情况二前一天为冷冻期第i天恰好未保持卖出的状态dp[i][1] dp[i - 1][3] - prices[i]; 因此dp[i][1] max(dp[i - 1][1], dp[i - 1][3] - prices[i]); 对于状态三第i天卖出股票前一天必为持有股票的状态即dp[i][2] dp[i - 1][0] prices[i]; 对于状态四冷冻期的前一天必定刚好卖出股票即dp[i][3] dp[i - 1][2];
3.初始化dp数组 第0天持有股票dp[0][0] 一定为-prices[0]卖出股票后不管是当天还是冷冻期以及保持卖出股票的状态所剩余的金钱一定都为0。 因此dp[0][0] -prices[0], dp[0][1] 0, dp[0][2] 0, dp[0][3] 0;
4.确定遍历顺序 从递归公式上可以看出dp[i] 依赖于 dp[i-1]所以是从前向后遍历。
5.打印dp数组 以 [1,2,3,0,2] 为例dp数组如下 算法实现
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(), vectorint (4,0));dp[0][0] -prices[0];for (int i 1; i prices.size(); 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[prices.size() - 1][1], max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));}
}; 714.买卖股票的最佳时机含手续费 题目链接 文章链接 前言 本题依然是买卖股票II的变形在原题的基础上增加手续费即可。
思路 dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金。 如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来
第i-1天就持有股票那么就保持现状所得现金就是昨天持有股票的所得现金 即dp[i - 1][0]第i天买入股票所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即dp[i - 1][1] - prices[i] 所以dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 如果第i天不持有股票即dp[i][1]的情况 依然可以由两个状态推出来
第i-1天就不持有股票那么就保持现状所得现金就是昨天不持有股票的所得现金 即dp[i - 1][1]第i天卖出股票所得现金就是按照今天股票价格卖出后所得现金注意这里需要有手续费了即dp[i - 1][0] prices[i] - fee 所以dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee); 算法实现
class Solution {
public:int maxProfit(vectorint prices, int fee) {vectorvectorint dp(prices.size(), vectorint (2, 0));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 max(dp[prices.size() - 1][0], dp[prices.size() - 1][1]);}
};
股票问题总结
