leetcode-714-线性DP-买卖股票的最佳时机含手续费

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 动态规划，优化空间复杂度
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if(prices.empty() || n == 1) return 0;

        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        for(int i = 0; i < n; ++i){
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee);
            dp_i_1 = max(dp_i_1, temp - prices[i]);
        } 

        return dp_i_0;
    }
};