algorithm004-01 · Yanun · Dec 15, 2019
diff --git a/Week 08/id_176/LeetCode_300_176.py b/Week 08/id_176/LeetCode_300_176.py
@@ -0,0 +1,10 @@
+cclass Solution:
+    def lengthOfLIS(self, nums: List[int]) -> int:
+        if not nums: return 0
+        length = len(nums)
+        dp = [1] * length
+        for i in range(length):
+            for j in range(i):
+                if nums[j] < nums[i]:
+                    dp[i] = max(dp[i], dp[j] + 1)
+        return max(dp)
diff --git a/Week 08/id_176/LeetCode_387_176.py b/Week 08/id_176/LeetCode_387_176.py
@@ -0,0 +1,10 @@
+class Solution:
+    def firstUniqChar(self, s: str) -> int:
+
+        count = collections.Counter(s)
+
+        for idx, ch in enumerate(s):
+            if count[ch] == 1:
+                return idx
+
+        return -1
diff --git a/Week 08/id_176/NOTE.md b/Week 08/id_176/NOTE.md
@@ -1,4 +1,34 @@
-# NOTE

-

+## 高级DP
+
+1. 状态拥有更多的维度
+2. 状态方程更为复杂
+3. 本质考察逻辑思维和数学能力等内功
+
+关键需要确定：
+
+1. 维度（定义、压缩）
+2. 状态转移方程
+3. 初始化和边界条件
+
+
+
+## 字符串匹配算法
+
+### 朴素算法
+
+遍历字符串的起始位置，挨个比较后面的所有字符是否与匹配字符串相同。
+
+### Rabin-Carp算法
+
+用hash值先过滤掉不可能相同的子串起点；如果hash值相同，再逐个字符比较。但如果每次都是先取子串再调用系统hash进行计算的话，因hash函数会遍历子串，复杂度其实还是O(mn)。使用滑动窗口进行加速：O(1)来更新hash值，从而整体上平均达到O(n)的复杂度。
+
+1. 假设子串的长度为M(pat)，目标字符串的长度为N(txt)
+2. 计算子串的hash值hash_pat
+3. 计算目标字符串txt中每个长度为M的子串的hash值（共需要计算N-M+1次）
+4. 比较hash值：如果hash值不同，字符串必然不匹配；如果hash值相同，还需要使用朴素算法再次判断。
+
+### KMP算法
+
+找已匹配片段最大前缀和最大后缀的最长长度。当知道在某个位置不匹配时，其实已经知道了前面能匹配的子串，可以利用已知匹配往后挪动