原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

解法1:

状态机模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
    相当于在之前状态转移的基础上 除了处理prices[i] 还要多一个处理手续费的过程
    统一将手续费的花销 放在买入的这个过程处理 
 */
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // 前i天 持股状态为j时 可获得的最大现金
        // j = 0 不持股 j = 1持股
        int [][] f = new int[n][2];    
        f[0][0] = 0;
        f[0][1] = -prices[0] - fee;

        for(int i = 1 ; i < n ; i++){
            f[i][0] = Math.max(f[i - 1][0],f[i - 1][1] + prices[i]);
            f[i][1] = Math.max(f[i - 1][1],f[i - 1][0] - prices[i] - fee);     
        }   

        return f[n - 1][0];   
    }
}