feat: $714

lucifer · lucifer · commit 9117cf1864eb · 2021-03-10T15:09:42.000+08:00
diff --git a/README.md b/README.md
@@ -294,12 +294,13 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [0560. 和为 K 的子数组](./problems/560.subarray-sum-equals-k.md)
 - [0609. 在系统中查找重复文件](./problems/609.find-duplicate-file-in-system.md)
 - [0611. 有效三角形的个数](./problems/611.valid-triangle-number.md)
-- [0673. 最长递增子序列的个数](./problems/673.number-of-longest-increasing-subsequence.md) 🆕
-- [0686. 重复叠加字符串匹配](./problems/686.repeated-string-match.md) 🆕
+- [0673. 最长递增子序列的个数](./problems/673.number-of-longest-increasing-subsequence.md)
+- [0686. 重复叠加字符串匹配](./problems/686.repeated-string-match.md)
 - [0718. 最长重复子数组](./problems/718.maximum-length-of-repeated-subarray.md)
+- [0714. 买卖股票的最佳时机含手续费](./problems/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md) 🆕
 - [0754. 到达终点数字](./problems/754.reach-a-number.md)
 - [0785. 判断二分图](./problems/785.is-graph-bipartite.md)
-- [0790. 多米诺和托米诺平铺](./problems/790.domino-and-tromino-tiling.md) 🆕
+- [0790. 多米诺和托米诺平铺](./problems/790.domino-and-tromino-tiling.md)
 - [0799. 香槟塔](./problems/799.champagne-tower.md) 🆕
 - [0801. 使序列递增的最小交换次数](./problems/801.minimum-swaps-to-make-sequences-increasing.md) 🆕
 - [0816. 模糊坐标](./problems/816.ambiguous-coordinates.md)
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -184,8 +184,9 @@
   - [0560. 和为 K 的子数组](./problems/560.subarray-sum-equals-k.md)
   - [0609. 在系统中查找重复文件](./problems/609.find-duplicate-file-in-system.md)
   - [0611. 有效三角形的个数](./problems/611.valid-triangle-number.md)
-  - [0673. 最长递增子序列的个数](./problems/673.number-of-longest-increasing-subsequence.md) 🆕
-  - [0686. 重复叠加字符串匹配](./problems/686.repeated-string-match.md) 🆕
+  - [0673. 最长递增子序列的个数](./problems/673.number-of-longest-increasing-subsequence.md)
+  - [0686. 重复叠加字符串匹配](./problems/686.repeated-string-match.md)
+  - [0714. 买卖股票的最佳时机含手续费](./problems/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md) 🆕
   - [0718. 最长重复子数组](./problems/718.maximum-length-of-repeated-subarray.md)
   - [0754. 到达终点数字](./problems/754.reach-a-number.md)
   - [0785. 判断二分图](./problems/785.is-graph-bipartite.md)
diff --git a/problems/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md b/problems/714.best-time-to-buy-and-sell-stock-with-transaction-fee.md
@@ -0,0 +1,176 @@
+## 题目地址(714. 买卖股票的最佳时机含手续费)
+
+https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
+
+## 题目描述
+
+```
+给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
+
+你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
+
+返回获得利润的最大值。
+
+注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
+
+示例 1:
+
+输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
+输出: 8
+解释: 能够达到的最大利润:
+在此处买入 prices[0] = 1
+在此处卖出 prices[3] = 8
+在此处买入 prices[4] = 4
+在此处卖出 prices[5] = 9
+总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
+
+注意:
+
+0 < prices.length <= 50000.
+0 < prices[i] < 50000.
+0 <= fee < 50000.
+```
+
+## 前置知识
+
+- 动态规划
+
+## 公司
+
+- 暂无
+
+## 记忆化递归
+
+### 思路
+
+首先明确一点。 如果没有交易费用，那么和另一道力扣的简单难度题目一样。 多了交易费用导致问题稍微复杂了一点。加了交易费用有什么不同呢？
+
+举一个例子大家就明白了。 比如 prices = [1,1,2,2,6] fee = 3。 如果没有按照无交易费的原则**只要有利可图就交易**，那么我们的收益为 1。实际上，在 1 买入， 6 卖出却可以得到 3 的收益。其根本原因在于**交易次数对结果是有影响的**。
+
+这道题不能使用上述的贪心策略，而必须使用动态规划。
+
+> 动态规划和贪心有着很强的关联性。
+
+定义 dp[i] 为到第 i 天(0=< i <n)为止的收益，那么答案就是 dp[n-1]。但是由于题目限定了只能**在手上没有股票的时候才能买，手上有股票的时候才能卖（这很显然）**。因此我们需要多定义一个维度的状态，表示现在手上是否有股票。标识是否手上有股票只需要一个长度为 2 的列表就可以了。
+
+因此我们可以使用 dp[i][0] 表示没有股票的情况下的最大利润，dp[i][1] 表示有股票的情况下的最大利润。
+
+那么：
+
+- 如果第 i 天手上没有股票，要么是 i - 1 没股票，今天什么都不做。要么是 i - 1 手上有股票，今天卖了它。因此 dp[i][0] 就是这两种情况的利润最大值。
+
+- 如果第 i 天手上有股票，要么是 i - 1 有股票，今天什么都不做。要么是 i - 1 手上没有股票，今天买了它。因此 dp[i][0] 就是这两种情况的利润最大值。
+
+最后返回 dp[n-1][0] 即可。
+
+> 由于 dp[n-1][1] <= dp[n-1][0] ，因此直接返回 dp[n-1][0] 即可。
+
+base case 见下方代码的递归出口。
+
+### 关键点
+
+- 记忆化递归
+
+### 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+
+class Solution:
+    def maxProfit(self, prices: List[int], fee: int) -> int:
+        def dp(i):
+            if i == 0:
+                return 0, -prices[0] - fee
+            sell, buy = dp(i - 1)
+            return max(sell, buy + prices[i]), max(buy, sell - prices[i] - fee)
+
+        return dp(len(prices) - 1)[0]
+
+```
+
+**复杂度分析**
+
+令 n 为数组长度。
+
+- 时间复杂度：$O(n)$
+- 空间复杂度：$O(n)$
+
+## DP
+
+### 思路
+
+使用 dp 的思路和上面一样，只是代码形式不同而已。
+
+### 关键点
+
+- 滚动数组优化技巧
+
+### 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```py
+
+class Solution:
+    def maxProfit(self, prices: List[int], fee: int) -> int:
+        n = len(prices)
+        dp = [[0 for i in range(2)]] * n
+        for i in range(n):
+            if i == 0:
+                dp[i][0] = 0
+                dp[i][1] = -1 * prices[i]
+            else:
+                dp[i][0] = max(dp[i - 1][1] + prices[i] - fee, dp[i - 1][0])
+                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
+
+        return dp[-1][0]
+
+```
+
+**复杂度分析**
+
+令 n 为数组长度。
+
+- 时间复杂度：$O(n)$
+- 空间复杂度：$O(n)$
+
+使用 DP 数组的好处就是可以使用滚动数组优化。比如这道题使用滚动数组可将空间进一步压缩。
+
+```py
+class Solution:
+    def maxProfit(self, prices: List[int], fee: int) -> int:
+        n = len(prices)
+        # [手里没股票, 手里有股票]
+        dp = [0, 0]
+        for i in range(n):
+            if i == 0:
+                dp[0] = 0
+                dp[1] = -1 * prices[i] - fee
+            else:
+                dp[0] = max(dp[0], dp[1] + prices[i])
+                dp[1] = max(dp[1], dp[0] - prices[i] - fee)
+
+        return dp[0]
+```
+
+**复杂度分析**
+
+令 n 为数组长度。
+
+- 时间复杂度：$O(n)$
+- 空间复杂度：$O(1)$
+
+> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
+
+力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~
+
+以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
