按照作者算法，添加了Python3 代码对“动态规划博弈”和“最长递增子序列” (labuladong#339)

Miraclemin · web-flow · commit c14be726447f · 2020-06-24T12:38:17.000+08:00
* Python3

* add Python3

* add Python3

* add Python3

* add Python3
diff --git a/动态规划系列/动态规划之博弈问题.md b/动态规划系列/动态规划之博弈问题.md
@@ -187,8 +187,37 @@ int stoneGame(int[] piles) {
 
 ![labuladong](../pictures/labuladong.png)
 
+[Hanmin](https://github.com/Miraclemin/) 提供 Python3 代码:
+
+```python
+def stoneGame(self, piles:List[int]) -> int:
+    n = len(piles)
+    ##初始化dp数组，用三维数组表示
+    dp = [[[0,0] for _ in range(0,n)] for _ in range(n)]
+    ##填入base case
+    for i in range(0,n):
+        dp[i][i][0] = piles[i]
+        dp[i][i][1] = 0
+    ##斜着遍历数组
+    for l in range(2,n+1):
+        for i in range(0,n-l+1):
+            j = l + i - 1
+            ##先手选择最左边或者最右边的分数
+            left = piles[i] + dp[i+1][j][1]
+            right = piles[j] + dp[i][j-1][1]
+            ##套用状态转移方程
+            if left > right:
+                dp[i][j][0] = left
+                dp[i][j][1] = dp[i+1][j][0]
+            else:
+                dp[i][j][0] = right
+                dp[i][j][1] = dp[i][j-1][0]
+    res = dp[0][n-1]
+    return res[0] - res[1]
+```
+
 [上一篇：动态规划之子序列问题解题模板](../动态规划系列/子序列问题模板.md)
 
 [下一篇：贪心算法之区间调度问题](../动态规划系列/贪心算法之区间调度问题.md)
 
-[目录](../README.md#目录)
+[目录](../README.md#目录)
diff --git a/动态规划系列/动态规划设计：最长递增子序列.md b/动态规划系列/动态规划设计：最长递增子序列.md
@@ -186,6 +186,54 @@ public int lengthOfLIS(int[] nums) {
 
 ![labuladong](../pictures/labuladong.jpg)
 
+[Hanmin](https://github.com/Miraclemin/) 提供 Python3 代码:
+
+**动态规划解法**
+
+``` python
+def lengthOfLIS(self, nums: List[int]) -> int:
+    n = len(nums)
+    ## dp 数组全部初始化为1
+    dp = [1 for x in range(0,n)]
+    for i in range(0,n):
+        for j in range(0,i):
+            if nums[i] > nums[j]:
+                dp[i] = max(dp[i],dp[j]+1)
+    res = 0
+    for temp in dp:
+        res = max(temp,res)
+    return res
+```
+**二分查找解法**
+
+```python
+def lengthOfLIS(self, nums: List[int]) -> int:
+    top = []
+    ##牌堆初始化为0
+    piles = 0
+    for num in nums:
+    ## num为要处理的扑克牌
+    
+    ##二分查找
+        left, right = 0, piles
+        while left < right:
+            mid = (left + right ) // 2
+            ##搜索左侧边界
+            if top[mid] > num:
+                right = mid
+            ##搜索右侧边界
+            elif top[mid] < num:
+                left = mid + 1
+            else:
+                right = mid
+        if left == piles:
+            ##没有找到合适的堆，新建一堆
+            piles += 1
+            ##把这张牌放到牌堆顶
+        top[left] = num
+    return piles
+    ##牌堆数就是LIS的长度
+```
 
 [上一篇：动态规划答疑篇](../动态规划系列/最优子结构.md)
 
diff --git a/动态规划系列/编辑距离.md b/动态规划系列/编辑距离.md
@@ -322,6 +322,37 @@ public:
     }
 };
 ```
+
+[Hanmin](https://github.com/Miraclemin/) 提供 Python3 代码:
+
+```python
+def minDistance(self, word1: str, word2: str) -> int:
+    m, n= len(word1), len(word2)
+    dp = [[0 for i in range(0,n+1)] for j in range(0,m+1)]
+    for i in range(1,m+1):
+        dp[i][0] = i ##base case:当s2为空，s1需要删除所有的字符
+    for j in range(1,n+1):
+        dp[0][j] = j ##base case:当s1为空，需要插入所有s2的字符
+    for i in range(1,m+1):
+        for j in range(1,n+1):
+            if word1[i-1] == word2[j-1]: ##当前字符一样
+                dp[i][j] = dp[i-1][j-1]
+            else:
+                dp[i][j] = min(
+                    dp[i-1][j]+1, 
+                    ##删除s1字符操作，可以理解为我直接把 s1[i] 
+                    ##这个字符删掉，前移 i，继续跟 j 对比，操作数加一
+                    dp[i][j-1]+1,
+                    ##增加s1字符操作，可以理解为我直接在s1[i]插入一个和s2[j]一样的字符
+                    ##s2[j]被匹配，那么前移 j，继续跟 i 对比，操作数加一
+                    dp[i-1][j-1]+1 
+                    ##修改s1字符操作，可以理解为我直接替换s1[i]为s2[j]一样的字符
+                    ##s2[j]被匹配，那么前移 i，j，操作数加一
+                )
+                
+    return dp[m][n] ##返回s1,s2最小的编辑距离
+```
+
 [上一篇：动态规划设计：最长递增子序列](../动态规划系列/动态规划设计：最长递增子序列.md)
 
 [下一篇：经典动态规划问题：高楼扔鸡蛋](../动态规划系列/高楼扔鸡蛋问题.md)
