LeetCode 714 Best Time to Buy and Sell Stock with Transaction Fee
题目分析
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
这次每次交易后有费率,同样是无限交易次数。
动态规划法
懒得解释了,直接看同 tag 下其他问题的解释吧,这里唯一要注意的是,我们不能直接将 dp[0][1] 设置为 INT_MIN, 因为考虑到要减去 fee,可能导致溢出。
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
vector<vector<int>> dp(prices.size() + 1, vector<int>(2, 0));
dp[0][1] = INT_MIN + fee;
for (int i = 1; i <= prices.size(); i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1] - fee);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]);
}
return dp[prices.size()][0];
}
};
Links: leetcode-714-best-time-to-buy-and-sell-stock-with-transaction-fee