六周作业

YujueY · YujueY · commit 68ff66d15ebc · 2020-07-18T21:43:59.000+08:00
diff --git a/Week06/1143.py b/Week06/1143.py
@@ -0,0 +1,13 @@
+class Solution:
+    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
+        if not text1 or not text2:
+            return 0
+        m, n = len(text1), len(text2)
+        dp = [[0] * (n + 1) for _ in range(m + 1)]
+        for i in range(1, m + 1):
+            for j in range(1, n + 1):
+                if text1[i - 1] == text2[j - 1]:
+                    dp[i][j] = dp[i - 1][j - 1] + 1
+                else:
+                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
+        return dp[m][n]
diff --git a/Week06/62.py b/Week06/62.py
@@ -0,0 +1,11 @@
+class Solution:
+    def uniquePaths(self, m: int, n: int) -> int:
+        if not m or not n:
+            return 0
+
+        dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
+
+        for i in range(1, m):
+            for j in range(1, n):
+                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
+        return dp[-1][-1]
diff --git a/Week06/64.py b/Week06/64.py
@@ -0,0 +1,14 @@
+class Solution:
+    def minPathSum(self, grid: List[List[int]]) -> int:
+        dp = grid
+        for i in range(len(grid)):
+            for j in range(len(grid[0])):
+                if i == j == 0:
+                    continue
+                elif i == 0:
+                    dp[i][j] = dp[i][j-1] + grid[i][j]
+                elif j == 0:
+                    dp[i][j] = dp[i-1][j] + grid[i][j]
+                else:
+                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
+        return dp[-1][-1]
diff --git a/Week06/91.py b/Week06/91.py
@@ -0,0 +1,21 @@
+def numDecodings(s: str) -> int:
+    pre = 1
+    cur = 1
+    if s[0] == "0":
+        return 0
+    for i in range(1, len(s)):
+        if s[i] == "0":
+            if s[i - 1] == "1" or s[i - 1] == "2":
+                cur = pre
+            else:
+                return 0
+        else:
+            if s[i - 1] == "1" or (s[i - 1] == "2" and "1" <= s[i] <= "6"):
+                temp = cur
+                cur += pre
+                pre = temp
+            else:
+                pre = cur
+                cur = cur
+
+    return cur
diff --git a/Week06/NOTE.md b/Week06/NOTE.md
@@ -1 +1,5 @@
-学习笔记
+学习笔记
+动态规划
+1.最优子结构
+2.储存中间状态
+3.DP方程
