广州仿站定制模板建站,wordpress最大图片尺寸,网站 mysql数据库 字符,新产品招区域总代理一、309.最佳买卖股票时机含冷冻期 题目链接/文章讲解#xff1a;代码随想录 视频讲解#xff1a;动态规划来决定最佳时机#xff0c;这次有冷冻期#xff01;| LeetCode#xff1a;309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 思考#xff1a; 1.确定dp数组代码随想录 视频讲解动态规划来决定最佳时机这次有冷冻期| LeetCode309.买卖股票的最佳时机含冷冻期_哔哩哔哩_bilibili 思考 1.确定dp数组dp table以及下标的含义 dp[i][j]第i天状态为j所剩的最多现金为dp[i][j] 具体可以区分出如下四个状态 状态一持有股票状态今天买入股票或者是之前就买入了股票然后没有操作一直持有不持有股票状态这里就有两种卖出股票状态 状态二保持卖出股票的状态两天前就卖出了股票度过一天冷冻期。或者是前一天就是卖出股票状态一直没操作状态三今天卖出股票状态四今天为冷冻期状态但冷冻期状态不可持续只有一天 本题为什么要单独列出「今天卖出股票」 一个状态呢 因为本题我们有冷冻期而冷冻期的前一天只能是 「今天卖出股票」状态如果是 「不持有股票状态」那么就很模糊因为不一定是 卖出股票的操作。 2.确定递推公式 状态一 达到买入股票状态即dp[i][0]有两个具体操作 操作一前一天就是持有股票状态状态一dp[i][0] dp[i - 1][0]操作二今天买入了有两种情况 前一天是冷冻期状态四dp[i - 1][3] - prices[i]前一天是保持卖出股票的状态状态二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]有两个具体操作 操作一前一天就是状态二操作二前一天是冷冻期状态四 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] 4.确定遍历顺序 从前向后 5.举例推导dp数组 代码实现
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]));}
};
时间复杂度O(n)空间复杂度O(n) 二、714.买卖股票的最佳时机含手续费 题目链接/文章讲解代码随想录 视频讲解动态规划来决定最佳时机这次含手续费| LeetCode714.买卖股票的最佳时机含手续费_哔哩哔哩_bilibili 思考 相对于动态规划122.买卖股票的最佳时机II本题只需要在计算卖出操作的时候减去手续费就可以了代码几乎是一样的。 dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee); 代码实现
class Solution {
public:int maxProfit(vectorint prices, int fee) {int n prices.size();vectorvectorint dp(n, vectorint(2, 0));dp[0][0] - prices[0]; // 持股票for (int i 1; i n; 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[n - 1][0], dp[n - 1][1]);}
};
时间复杂度O(n)空间复杂度O(n) 三、总结 题目链接/文章讲解代码随想录
