目录
- 1.买卖股票的最佳时机含冷冻期
- 1.题目链接
- 买卖股票的最佳时机含冷冻期
- 2.算法原理详解
- 3.代码实现
- 2.买卖股票的最佳时机含手续费
- 1.题目链接
- 2.算法原理详解
- 3.代码实现
1.买卖股票的最佳时机含冷冻期
买卖股票的最佳时机含冷冻期
2.算法原理详解
- 思路:
-
确定状态表示 ->
dp[i][j]
的含义:i
-> 到了哪天,j
-> 当天处于什么状态dp[i][0]
:第i
天结束之后,处于"买入"状态,此时的最大利润dp[i][1]
:第i
天结束之后,处于"可交易"状态,此时的最大利润dp[i][2]
:第i
天结束之后,处于"冷冻期"状态,此时的最大利润
-
推导状态转移方程:本题关系复杂,可以画图辅助
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - p[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2])
dp[i][2] = dp[i - 1][0] + p[i]
-
初始化:
dp[0][0] = -p[0], dp[0][1] = dp[0][2] = 0
-
确定填表顺序:从左往右,一次填写三个表
-
确定返回值:
max(dp[n - 1][1], dp[n - 2][2])
-
3.代码实现
int maxProfit(vector<int>& prices)
{int n = prices.size();vector<vector<int>> dp(n, vector<int>(3));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][2]);dp[i][2] = dp[i - 1][0] + prices[i];}return max(dp[n - 1][1], dp[n - 1][2]);
}
2.买卖股票的最佳时机含手续费
1.题目链接
- 买卖股票的最佳时机含手续费
2.算法原理详解
- 思路:
-
确定状态表示 ->
dp[i]
的含义- 第
i
天结束之后,所能获得的最大利润 - 本题,状态表示还可以继续细分:
f[i]
:第i
天结束之后,处于“买入”状态,此时的最大利润g[i]
:第i
天结束之后,处于“卖出”状态,此时的最大利润
- 第
-
推导状态转移方程:本题关系复杂,可以画图辅助
f[i] = max(f[i - 1], g[i - 1] - p[i])
g[i] = max(g[i - 1], f[i - 1] + p[i] - fee)
-
初始化:
f[0] = -p[0], g[0] = 0
-
确定填表顺序:从左往右,两个表一起填
-
确定返回值:
g[n - 1]
-
3.代码实现
int maxProfit(vector<int>& prices, int fee)
{int n = prices.size();vector<int> f(n); // 买入vector<int> g(n); // 卖出f[0] = -prices[0];for(int i = 1; i < n; i++){f[i] = max(f[i - 1], g[i - 1] - prices[i]);g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);}return g[n - 1];
}