309. 最佳买卖股票时机含冷冻期 - 力扣（Leetcode）
思路:
-
使用动态规划
-
-
确定dp数组以及下标的含义
dp[i][j]的定义为：dp[i][0]的意思是今日保持股票买入的状态dp[i][1]的意思是今日保持股票卖出的状态dp[i][2]的意思是今日卖出股票dp[i][3]的意思是今日在股票购买冷却状态中
-
确定递推公式
// 状态转移方程 // dp[i][0]有三种操作 // 第一种是昨天就已经买入了 // 第二种是昨天是股票卖出的状态 // 第三种是昨天是股票在购买冷却的状态，要取三种状态的最大值 dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1] - prices[i]), dp[i - 1][3] - 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数组如何初始化
vector< vector<int> > dp(len, vector<int>(4, 0)); // 只需要初始化第一天买入为-prices[0] dp[0][0] = -prices[0]; // 其他都初始化为0 -
确定遍历顺序
// 因为 i = 0 已经初始化，所以从 i = 1 开始
-
我的AC代码
高空间复杂度
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector< vector<int> > dp(len, vector<int>(4, 0));
dp[0][0] = -prices[0];
for(int i = 1; i < len; ++i) {
dp[i][0] = max(max(dp[i - 1][0], 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[len - 1][1], max(dp[len - 1][2], dp[len - 1][3]));
}
};优化空间复杂度
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector< vector<int> > dp(2, vector<int>(4, 0));
dp[0][0] = -prices[0];
for(int i = 1; i < len; ++i) {
dp[i % 2][0] = max(max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]), dp[(i - 1) % 2][3] - prices[i]);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][3]);
dp[i % 2][2] = dp[(i - 1) % 2][0] + prices[i];
dp[i % 2][3] = dp[(i - 1) % 2][2];
}
return max(dp[(len - 1) % 2][1], max(dp[(len - 1) % 2][2], dp[(len - 1) % 2][3]));
}
};标准答案
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(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]));
}
};714. 买卖股票的最佳时机含手续费 - 力扣（Leetcode）
思路:
-
使用动态规划
-
-
确定dp数组以及下标的含义
dp[i]的定义为：dp[0]的意思是持有股票的最大现金dp[1]的意思是不持有股票的最大现金
-
确定递推公式
// 状态转移方程 // dp[0]有两种操作 // 第一种是昨天已经持有股票了 // 第二种是今天购买股票，要算上手续费 dp[0] = max(dp[0], dp[1] - prices[i] - fee); // dp[1]有两种操作 // 第一种是昨天已经不持有股票了 // 第二种是今天卖出股票 dp[1] = max(dp[1], dp[0] + prices[i]); -
dp数组如何初始化
vector<int> dp(2, 0); // 只需要初始化持有股票的状态 dp[0] = -prices[0] - fee; // 不持有股票的状态默认初始化为0 -
确定遍历顺序
因为已经初始化 i = 0 了，所以从 i = 1 开始
-
我的AC代码
/*
其实只需要一维数组就能解决问题，我们分情况来看。如果是dp[1]，那么有两种操作，一种是昨天就已经买了股票，保持原样，那么其实可以直接和自己比，即dp[0] = dp[0]；还有一种操作是今天买股票，那么就要继承dp[1]，即手上没有股票时的金额，然后减去prices[i]和fee，因为dp[0]的语句顺序在dp[1]前面，所以此时的dp[1]就是昨天的dp[1]，所以可以直接用，那么dp[0]的状态转移方程就写成了dp[0] = max(dp[0], dp[1] - prices[i] - fee);，对于dp[1]来说也是同理，一种操作是和昨天一样手上没有股票，那么就和自己比，即dp[1] = dp[1]，还有一种就是今天把股票卖了，所以要继承dp[0]的情况，dp[0]无非就两种，一种是之前就买了股票，所以do[1]这边就相当于之前买了股票，今天卖了，另一种情况是dp[0]今天买了股票，那么dp[1]今天再把股票卖掉，就相当于今天买今天卖，代码逻辑上 也是通顺的，无非是今天买今天卖多次一举。所以dp[1]的状态转移方程就写成dp[1] = max(dp[1], dp[0] + prices[i]);
*/
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
vector<int> dp(2, 0);
dp[0] = -prices[0] - fee;
for(int i = 1; i < prices.size(); ++i) {
dp[0] = max(dp[0], dp[1] - prices[i] - fee);
dp[1] = max(dp[1], dp[0] + prices[i]);
}
return dp[1];
}
};滚动数组
//之所以可以使用滚动数组是因为递推公式只依赖前一天的结果，所以只需要保存两天即可
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int len = prices.size();
vector< vector<int> > dp(2, vector<int>(2, 0));
dp[0][0] = -prices[0] - fee;
for(int i = 1; i < len; ++i) {
dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i] - fee);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
}
return dp[(len - 1) % 2][1];
}
};标准答案
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(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]);
}
};
Comments NOTHING