买卖股票的最佳时机含手续费
Leetcode 714
学习记录自代码随想录
要点：1.两种状态持有股票和不持有股票；
2.递推公式
d
p
[
i
]
[
0
]
=
m
a
x
(
d
p
[
i
−
1
]
[
0
]
,
d
p
[
i
−
1
]
[
1
]
−
p
r
i
c
e
s
[
i
]
)
d
p
[
i
]
[
1
]
=
m
a
x
(
d
p
[
i
−
1
]
[
1
]
,
d
p
[
i
−
1
]
[
0
]
+
p
r
i
c
e
s
[
i
]
−
f
e
e
)
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)
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)文章来源：https://www.toymoban.com/news/detail-845546.html
3.dp数组初始化，
d
p
[
i
]
[
0
−
1
]
dp[i][0-1]
dp[i][0−1]代表利润，所以不持有股票后利润最小为0，
初始化为
d
p
[
0
]
[
0
]
=
−
p
r
i
c
e
s
[
0
]
，
d
p
[
0
]
[
1
]
=
0
dp[0][0] = -prices[0]，dp[0][1] = 0
dp[0][0]=−prices[0]，dp[0][1]=0文章来源地址https://www.toymoban.com/news/detail-845546.html
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
// 1.dp[i][0-1] 0:代表持有股票，1代表不持有股票
vector<vector<int>> dp(n, vector<int>(2, 0));
// 2.递推公式：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)
// 3.dp数组初始化
dp[0][0] = -prices[0];
dp[0][1] = 0; // 因为是利润，所以不能初始化为-fee
// 4.遍历顺序：正向遍历
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);
}
// 5.举例推导dp数组
return max(0, max(dp[n-1][0], dp[n-1][1]));
}
};
到了这里，关于动态规划 Leetcode 714 买卖股票的最佳时机含手续费的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![算法[动态规划]---买卖股票最佳时机](https://imgs.yssmx.com/Uploads/2024/02/708618-1.png)
