Python3

Miraclemin · labuladong · commit 032bc7e6798b · 2020-06-22T20:47:38.000+08:00
diff --git a/动态规划系列/团灭股票问题.md b/动态规划系列/团灭股票问题.md
@@ -391,9 +391,86 @@ int maxProfit_k_any(int max_k, int[] prices) {
 **致力于把算法讲清楚！欢迎关注我的微信公众号 labuladong，查看更多通俗易懂的文章**：
 
 ![labuladong](../pictures/labuladong.png)
-
+[Hanmin](https://github.com/Miraclemin/) 提供 Python3 代码:
+**第一题，k = 1**
+```python
+def maxProfit(self, prices: List[int]) -> int:
+    dp_i_0,dp_i_1 = 0,float('-inf')
+    for price in prices:
+        dp_i_0 = max(dp_i_0, dp_i_1 + price)
+        dp_i_1 = max(dp_i_1, -price)
+    return dp_i_0
+```
+**第二题，k = +infinity**
+```python
+def maxProfit_k_inf(self, prices: List[int]) -> int:
+    dp_i_0,dp_i_1 = 0,float('-inf')
+    for price in prices:
+        temp = dp_i_0
+        dp_i_0 = max(dp_i_0, dp_i_1 + price)
+        dp_i_1 = max(dp_i_1, temp - price)
+    return dp_i_0
+```
+**第三题，k = +infinity with cooldown**
+```python
+def maxProfit_with_cool(self, prices: List[int]) -> int:
+    dp_i_0,dp_i_1 = 0,float('-inf')
+    dp_pre_0 = 0 ##代表 dp[i-2][0]
+    for price in prices:
+        temp = dp_i_0
+        dp_i_0 = max(dp_i_0, dp_i_1 + price)
+        dp_i_1 = max(dp_i_1, dp_pre_0 - price)
+        dp_pre_0 = temp
+    return dp_i_0
+```
+**第四题，k = +infinity with fee**
+```python
+def maxProfit_with_fee(self, prices: List[int], fee: int) -> int:
+    dp_i_0,dp_i_1 = 0,float('-inf')
+    for price in prices:
+        temp = dp_i_0
+        dp_i_0 = max(dp_i_0, dp_i_1 + price)
+        dp_i_1 = max(dp_i_1, temp - price -fee)
+    return dp_i_0
+```
+**第五题，k = 2**
+```python
+def maxProfit_k_2(self, prices: List[int]) -> int:
+    dp_i10,dp_i11 = 0,float('-inf')
+    dp_i20,dp_i21 = 0,float('-inf')
+    for price in prices:
+        dp_i20 = max(dp_i20, dp_i21 + price)
+        dp_i21 = max(dp_i21, dp_i10 - price)
+        dp_i10 = max(dp_i10, dp_i11 + price)
+        dp_i11 = max(dp_i11, -price)
+    return dp_i20
+```
+**第六题，k = any integer**
+```python
+def maxProfit_k_any(self, max_k: int, prices: List[int]) -> int:
+    n = len(prices)
+    if max_k > n // 2:
+        return self.maxProfit_k_inf(prices)
+    else:
+        dp = [[[None, None] for _ in range(max_k + 1)] for _ in range(n)]
+        for i in range(0,n):
+            for k in range(max_k,0,-1):
+                if i-1 == -1:## 处理 base case
+                    dp[i][k][0] = 0
+                    ## 解释：
+                    ## dp[i][k][0] = max(dp[-1][k][0], dp[-1][k][1] + prices[i])
+                    ## = max(0, -infinity + prices[i]) = 0
+                    dp[i][k][1] = -prices[i]
+                    ## 解释：
+                    ## dp[i][1] = max(dp[-1][k][1], dp[-1][k][0] - prices[i])
+                    ## = max(-infinity, 0 - prices[i]) = -prices[i]
+                    continue
+                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
+                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
+        return dp[n - 1][max_k][0];
+```
 [上一篇：动态规划之KMP字符匹配算法](../动态规划系列/动态规划之KMP字符匹配算法.md)
 
 [下一篇：团灭 LeetCode 打家劫舍问题](../动态规划系列/抢房子.md)
 
-[目录](../README.md#目录)
+[目录](../README.md#目录)
