学校网站建设招聘,上海网页制作,自建网站备案通过后怎么做,购物网站英文介绍算法学习day511.力扣309.最佳买卖股票时机含冷冻期1.1 题目描述1.2分析1.3 代码2.力扣714.买卖股票的最佳时机含手续费2.1 题目描述2.2 分析2.3 代码3.参考资料1.力扣309.最佳买卖股票时机含冷冻期
1.1 题目描述
题目描述
给定一个整数数组#xff0c;其中第i个元素代表了第…
算法学习day511.力扣309.最佳买卖股票时机含冷冻期1.1 题目描述1.2分析1.3 代码2.力扣714.买卖股票的最佳时机含手续费2.1 题目描述2.2 分析2.3 代码3.参考资料1.力扣309.最佳买卖股票时机含冷冻期
1.1 题目描述
题目描述
给定一个整数数组其中第i个元素代表了第i天的股票价格。
设计一个算法求最大利润。在满足以下约束条件下尽可能多的完成交易
(1)你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)
(2)卖出股票后你无法在第二天买入股票(冷冻期为1天)
例
输入[1,2,3,0,2]
输出3
解释:对应的交易状态为:[买入卖出冷冻期买入卖出]
1.2分析
动规五部曲
1.确定dp数组以及下标的含义
dp[i] [j]:第i天状态为j,所剩的最多现金为dp[i] [j]
dp[i] [0]: 持有股票今天买入股票或者之前买入后没有操作了一直持有
dp[i] [1]保持卖出股票的状态度过了冷冻起之后一直没有操作
dp[i] [2]今天卖出股票
dp[i] [3]: 今天为冷冻期但冷冻期状态不可持续
2.确定递推公式
dp[i] [0]: 持有股票今天买入股票或者之前买入后没有操作了一直持有
(1)前一天持有股票的状态dp[i] [0] dp[i - 1] [0]
(2)今天买入
(2.1)前一天是冷冻期然后今天买入,dp[i - 1] [3] - prices[i]
(2.2)前一天保持卖出股票状态dp[ i -1] [1] - prices[i]
递推公式: dp[i] [0] max(dp[i - 1] [0] , dp[i - 1] [3] - prices[i] , dp[ i -1] [1] - prices[i])
**dp[i] [1]**保持卖出股票的状态度过了冷冻起之后一直没有操作
(1) 前一天就卖出股票了
(2) 前一天是冷冻期
递推公式: 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]
dp[0] [1] 0
dp[0] [2] 0
dp[0] [3] 0
4.确定遍历顺序
显然从前往后遍历
5.举例推导dp数组
1.3 代码
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();if (n 0) return 0;vectorvectorint dp(n, vectorint(4, 0)); // 创建一个 n 行 4 列的二维数组 dp用于记录各个状态下的最大收益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])); }
};
2.力扣714.买卖股票的最佳时机含手续费
2.1 题目描述
题目描述
给定一个整数数组prices , 其中第i个元素代表了第i天的股票价格非负整数fee代表了交易的手续费。
可以无限次交易但是每一笔交易都需要手续费。如果你已经购买了一个股票在卖出它之前不能在继续购买股票了。
返回获得利润的最大值。
例
输入prices [1, 3, 2, 8, 4, 9] , fee 2
输出 8
在此处买入 prices[0] 1在此处卖出 prices[3] 8在此处买入 prices[4] 4在此处卖出 prices[5] 9总利润: ((8 - 1) - 2) ((9 - 4) - 2) 8.
2.2 分析
dp[i] [0] 表示第i天持有股票所省最多现金。dp[i] [1] 表示第i天不持有股票所得最多现金
1.dp[i] [0] 表示第i天持有股票所省最多现金由以下状态推导出来
(1) 第i -1 就持有股票保持现状所得现金就是昨天持有股票所得现金dp[i- 1] [0]
(2) 第i天买入股票所得现金就是昨天不持有股票的所得现金减去今天的股票价格dp[i - 1] [1] - prices[i]
递推公式dp[i] [0] max(dp[i-1] [0], dp[i - 1] [1] - prices[i])
2.dp[i] [1] 表示第i天不持有股票所得最多现金
(1)如果第i -1 就不持有股票保持现状所得现金就是昨天不持有股票的现金,dp[i-1] [1]
(2) 第i天卖出股票所得现金就是按照今天股票价格卖出后所得现金需要手续费dp[i - 1] [0] prices[i] - fee
递推公式:dp[ i ] [1] max(dp[i - 1] [1] , dp[ i- 1] [0] prices[i] - fee)
2.3 代码
class Solution {
public:int maxProfit(vectorint prices, int fee) {int n prices.size();// 定义 dp 数组dp[i][0/1] 表示第 i 天结束时// 持有股票/不持有股票的最大收益vectorvectorint dp(n, vectorint(2, 0));dp[0][0] - prices[0]; // 第一天持股花费 prices[0] 的成本for (int i 1; i n; i) {// 第 i 天结束时持有股票的最大收益分两种情况// 1. 前一天也持有股票今天不进行任何操作所以今天的最大收益就是昨天的最大收益// 2. 前一天不持有股票今天买入股票所以今天的最大收益就是前一天不持有股票时的最大收益减去今天的股票价格dp[i][0] max(dp[i - 1][0], dp[i - 1][1] - prices[i]);// 第 i 天结束时不持有股票的最大收益也分两种情况// 1. 前一天也不持有股票今天不进行任何操作所以今天的最大收益就是昨天的最大收益// 2. 前一天持有股票今天卖出股票所以今天的最大收益就是前一天持有股票时的最大收益加上今天的股票价格减去手续费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]);}
};
3.参考资料
[代码随想录]
