多状态动态规划之买卖股票的最佳时机含手续费

我就是我 2024-03-17 13:38 52阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [买卖股票的最佳时机含手续费][Link 1]  
![image.png][]  
根据示例 1 进行分析 :  
![image.png][image.png 1]  
示例 2 :  
![image.png][image.png 2]  
总的来说, 和我们之前的 " 最佳买卖股票 " 有点类似. 遵循以下规则

1.  当天手上没有股票可以选择不买入
2.  当天手上有股票可以选择不卖出
3.  当天手上没有股票可以选择买入
4.  手上有股票必须卖出才可以进行买入操作
5.  根据用户的不同操作, 尽可能的获得更多的利润. ( 低价收入高价卖出 )

PS : **这里的买入和卖出只得是一笔交易. 也就是说, 当你买入后再卖出时一瞬间会扣取手续费. 买入时并不会扣除, 只有卖掉股票时才会扣 !**

## 2. 状态表示 ##

以 i 为结尾, 表示从第一天到结束时, 所获得的最大利润  
不难发现, 当第 i 天结束的时候, 又有两种情况.

1.  第 i 天结束时为买入状态

这种情况, 我们以 f\[i\] 表示, 即从第一天开始到第 i 天结束时, 第 i 天处于买入状态时所获得的最大利润.

1.  第 i 天结束时为卖出状态

这种情况, 我们以 g\[i\] 表示, 即从第一天开始到第 i 天结束时, 第 i 天处于卖出转态时所获得的最大利润.

## 3. 状态转移方程 ##

根据上面两个状态表示可以看出, 这是一个多状态的问题. 因此我们对这两个状态分别进行状态转移方程的分析.  
![image.png][image.png 3]

1.  第 i 天结束时为买入状态

那么, 如何才能在第 i 天结束时为买入状态呢 ? 那我们就需要观察 i - 1 前一天的状态了.

1.  i - 1 为买入状态, 第 i 天不进行操作, 第 i 天结束后依然为买入状态

这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为买入状态时所获得的最大利润, 对应到状态表示中则为 f\[i-1\], 第 i 天由于不操作, 最终利润为 **f\[i-1\]**

1.  i - 1 为卖出状态, 第 i 天进行买入操作, 第 i 天结束后则为买入状态.

这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为卖出状态时所获得的最大利润, 对应到状态表示中则为 g\[i-1\], 并且在第 i 天买入, 最终利润为 **g\[i-1\]-prices\[i\]**

最终第 i 天结束时为买入状态的状态表示为 f\[i\] = Math.max(**g\[i-1\]-prices\[i\], f\[i-1\]), 为两种情况下的最大利润.**

1.  第 i 天结束时为卖出状态
    
    1.  i - 1 天为买入状态, 第 i 天进行卖出操作, 第 i 天结束后则为卖出状态

这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为卖出状态时所获得的最大利润, 对应到状态表示中则为 f\[i-1\], 由于在第 i 天进行卖出, 最终利润为 **f\[i-1\] + prices\[i\]-fee**

1.  i - 1 天为卖出状态, 第 i 天不进行操作, 则第 i 天接受后依然为卖出状态 ( 可交易 )

这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为卖出状态时所获得的最大利润, 对应到状态表示中则为 g\[i-1\], 由于第 i 天不进行操作. 因此最终利润为 **g\[i-1\]**

最终第 i 天结束时为卖出状态的状态表示为 g\[i\] = Math.max(**f\[i-1\] + prices\[i\]-fee, g\[i-1\]), 为两种情况下的最大利润**

## 4. 初始化 ##

根据状态转移方程, f\[0\] 和 g\[0\] 在填表时会发生越界错误, 因此需要单独进行初始化.  
如果第 1 天结束时为买入状态, 之后整个股票交易就结束了, 此时还没有卖出股票, 手上的利润为 **-prices\[0\] ( 负数 )**

**如果第 1 天结束时为卖出状态, 之后整个股票交易就结束了, 此时为 0 , 等同于这一天买入后又卖出去了. ( 这句话需要各位好好体会一下 )**

## 5. 填表顺序 ##

根据状态转移方程, 想要知道 i 位置结束时获得的最大利润, 要先知道前一天的最大利润. 因此填表顺序为从左往右

## 6. 返回值 ##

返回第 n 天结束时, 所获得的最大利润. 对应到我们的状态表示中则为两种不同状态下第 n 天的最大值. 即 Math.max(f\[n-1\], g\[n-1\]) **( 注意 n 为数组长度, 和下标的对应关系 )**

## 7. 代码演示 ##

class Solution {
        
        public int maxProfit(int[] prices, int fee) {
        
            
            // 1. 创建 dp 表
            int n = prices.length;
            int[] f = new int[n]; // i 位置结束时为买入状态所获得的最大利润
            int[] g = new int[n]; // i 位置结束时为卖出状态所获得的最大利润
    
            // 2. 初始化
            f[0] = -prices[0];
    
            // 3. 填写 dp 表
            for(int i = 1; i < n; i++) {
        
                 f[i] = Math.max(g[i - 1]-prices[i], f[i - 1]);
                 g[i] = Math.max(f[i - 1] + prices[i]-fee, g[i - 1]);
            }
    
            // 4. 确认返回值
            return Math.max(f[n - 1], g[n - 1]);
        }
    }

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/624266fd18fb4cae959625167566b549.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8807f7a102cd44ea83f4a79abf4c6baa.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/afbd17ce085c4f229fb75978e6aae887.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ac5b1cf3e7314addb4a58eb66f6644be.png