letcode每日一题-买卖股票的最佳时机含手续费

谁践踏了优雅 2022-12-28 14:12 154阅读 0赞

题目描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70][]

## 我的解题思路： ##

我们假设先持有第1个股票，如果有有比之价格低的就持有价格低的股票，如果 有比之大且收益大于0的情况我们就

走两个分支 ：1.抛售现在持有的股票 2.不抛售现在持有的股票，然后选择相对较大的收益，以此类类推,代码实现如下:

public int maxProfit(int[] prices, int fee) {
            return maxProfit(prices, fee,0,Integer.MAX_VALUE);
        }
    
        public int maxProfit(int[] prices, int fee,int begin,int min){
            for(int i=begin;i<prices.length;i++){
                if(min>prices[i]){
                    min=prices[i];
                }else if(prices[i]-min-fee>0) {
                    return Math.max(
                            prices[i]-min-fee+maxProfit(prices,fee,i+1,Integer.MAX_VALUE),  //抛售
                            maxProfit(prices,fee,i+1,min));   //不抛售
                }
            }
            return 0;
        }

但是这个实现在数据较多的时候就会应为递归的原因执行时间过长。

## 方法二 ##

摘自:[letcode题解][letcode]

考虑到「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。

定义状态 dp\[i\]\[0\] 表示第 i天交易完后手里没有股票的最大利润，dp\[i\]\[1\] 表示第 i天交易完后手里持有一支股票的最大利润（i 从 0 开始）。

考虑dp\[i\]\[0\] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp\[i−1\]\[0\]，或者前一天结

束的时候手里持有一支股票，即dp\[i−1\]\[1\]，这时候我们要将其卖出，并获得 prices\[i\] 的收益，但需要支付 fee 的手续费。因此为了收益

最大化，我们列出如下的转移方程：

dp\[i\]\[0\]=max\{dp\[i-1\]\[0\],dp\[i-1\]\[1\]+prices\[i\]-fee\}  
dp\[i\]\[0\]=max\{dp\[i−1\]\[0\],dp\[i−1\]\[1\]+prices\[i\]−fee\}

再来按照同样的方式考虑 dp\[i\]\[1\] 按状态转移，那么可能的转移状态为前一天已经持有一支股票，即dp\[i−1\]\[1\]，或者前一天结束时还没有股票，

即p\[i−1\]\[0\]，这时候我们要将其买入，并减少 prices\[i\] 的收益。可以列出如下的转移方程：

dp\[i\]\[1\]=max\{dp\[i-1\]\[1\],dp\[i-1\]\[0\]-prices\[i\]\}  
dp\[i\]\[1\]=max\{dp\[i−1\]\[1\],dp\[i−1\]\[0\]−prices\[i\]\}

对于初始状态，根据状态定义我们可以知道第 00 天交易结束的时候有dp\[0\]\[0\]=0  以及dp\[0\]\[1\]=−prices\[0\]。

因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候dp\[n−1\]\[0\] 的收益必

然是大于 dp\[n−1\]\[1\] 的，最后的答案即为dp\[n−1\]\[0\]。

代码实现如下:

public int maxProfit(int[] prices, int fee) {
            //db[i][0]  不持有 db[i][1] 持有
            int[][] db=new int[prices.length][2];
            db[0][0]=0;
            db[0][1]=-prices[0];
            for(int i=1;i<db.length;i++){
                db[i][0]=Math.max(db[i-1][0],db[i-1][1]+prices[i]-fee);
                db[i][1]=Math.max(db[i-1][1], db[i - 1][0]-prices[i]);
            }
            return db[prices.length - 1][0];
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYNTk5MQ_size_16_color_FFFFFF_t_70]: /images/20221120/db326cd58af349358780c683d0bf663d.png
[letcode]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-han-sh-rzlz/