网页设计网站概述怎么写,服务器站点的网站地图怎么做,国内搜索网站排名,照片生成视频制作软件目录 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费 股票问题总结 309.最佳买卖股票时机含冷冻期 题目链接#xff1a;309. 买卖股票的最佳时机含冷冻期 分为四种状态#xff1a; 0. 持有股票 1. 不持有股票——卖出状态 2. 不持有股票——今天卖出 3. 今天为… 目录 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费 股票问题总结 309.最佳买卖股票时机含冷冻期 题目链接309. 买卖股票的最佳时机含冷冻期 分为四种状态 0. 持有股票 1. 不持有股票——卖出状态 2. 不持有股票——今天卖出 3. 今天为冷冻期 1dp[ i ][ j ] 表示第 i 天的所拥有的钱j 表示状态 2dp[ i ][ 0 ] 有三种情况① 第 i - 1 天持有② 第 i - 1 天是卖出状态今天买入③第 i - 1 天是冷冻期今天买入 dp[ i ][ 1 ] 有两种状态① 第 i - 1 天是卖出状态以前就卖出② 第 i - 1 天是冷冻期前天刚卖出 dp[ i ][ 2 ] 有一种状态① 第 i - 1 天持有股票今天卖出 dp[ i ][ 3 ] 有一种状态① 第 i - 1 天卖出 3dp[ i ][ 0 ] -prices[ 0 ] 4按日期遍历 class Solution {
public:int maxProfit(vectorint prices) {int size prices.size();vectorvectorint dp(size,vectorint(4, 0));dp[0][0] -prices[0];for(int i 1; i size; 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] 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[size-1][1], max(dp[size-1][2], dp[size-1][3]));}
}; 714.买卖股票的最佳时机含手续费 题目链接714. 买卖股票的最佳时机含手续费 在买卖股票的最佳时机 Ⅱ 的基础上卖出时减去一个手续费即可 class Solution {
public:int maxProfit(vectorint prices, int fee) {vectorvectorint dp(2, vectorint(2, 0));dp[0][0] -prices[0];for(int i 1; i prices.size(); i){dp[i % 2][0] max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i]);dp[i % 2][1] max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] prices[i] - fee);}return dp[(prices.size() - 1) % 2][1];}
}; 股票问题总结 题型总结 只能买卖一次无限次买卖最多买卖两次最多买卖 k 次买卖多次卖出后有冷冻期买卖多次每次买卖有额外手续费 题型特点 设二维 dp数组记录状态有多少种状态数组的第二维就开多大空间联系不同状态之间的关系
