LeetCode-714. 买卖股票的最佳时机含手续费

青旅半醒 2024-03-26 20:41 64阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划

题目来源  
[714. 买卖股票的最佳时机含手续费][714.]

### 题目思路 ###

建议做一下LeetCode-122. 买卖股票的最佳时机 II，简直一摸一样  
[https://donglin.blog.csdn.net/article/details/129676556][https_donglin.blog.csdn.net_article_details_129676556]

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]\[0\]代表持有股票  
dp\[i\]\[1\]代表不持有股票

*  2.确定递推公式

dp\[i\]\[0\]:有两个状态，一个是保持前一天的持有的状态，另一个是买入(前一天不持有)  
dp\[i\]\[0\]:有两个状态，一个是保持前一天的不持有的状态，另一个是卖掉(前一天持有)，顺便要扣掉手续费

dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);  //持有
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);   //不持有

*  3.dp数组如何初始化

dp\[0\]\[0\]：表示持有，说明第一天要买入  
dp\[0\]\[1\]：表示不持有，说明当天买当天卖，即为0

dp[0][0] = - prices[0];
            dp[0][1] = 0;

*  4.确定遍历顺序

从递推公式可以看出dp\[i\]都是由dp\[i - 1\]推导出来的，那么一定是从前向后遍历。

*  5.举例推导dp数组

输入：prices = \[1, 3, 2, 8, 4, 9\], fee = 2  
输出：8  
![在这里插入图片描述][66d6c8196158439d940940cf018168d1.png]

[714.]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[https_donglin.blog.csdn.net_article_details_129676556]: https://donglin.blog.csdn.net/article/details/129676556
[66d6c8196158439d940940cf018168d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7071e972eed542dda204451c7166e30c.png