文檔講解：代碼隨想錄
視頻講解：代碼隨想錄B站賬號
狀態：看了視頻題解和文章解析后做出來了
392.判斷子序列?
class Solution:def isSubsequence(self, s: str, t: str) -> bool:dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]for i in range(1, len(s) + 1):for j in range(1, len(t) + 1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = dp[i][j-1]return dp[len(s)][len(t)] == len(s)- ??? 時間復雜度：O(n^2)
- ??? 空間復雜度：O(n)
1. 確定dp數組的含義
dp[i][j] 表示以下標i-1為結尾的字符串s，和以下標j-1為結尾的字符串t，相同子序列的長度為dp[i][j]
這里用i，j表示 i-1，j-1 是為了給初始化留一行和一列，而且遞推公式也更方便。
2. 確定遞推公式
第一種情況：s和j的元素相等，dp[i][j] 在 dp[i-1][j-1] 的基礎上 + 1
第二種情況：s和j元素不相等，相當于要刪除掉 j 的 i 位元素再去做對比，那就是 dp[i][j] = dp[i][j-1]
3. dp數組初始化
從遞推公式可以看出dp[i][j]都是依賴于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
4. 確定遍歷順序
遞推公式中的j是i和j之前的元素下標，所以從前往后遞推。
5. 舉例
?115.不同的子序列?
class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]for i in range(1, len(s) + 1):if t[0] == s[i-1]:dp[1][i] = dp[1][i-1] + 1else:dp[1][i] = dp[1][i-1]for i in range(2, len(t) + 1):for j in range(1, len(s) + 1):if t[i-1] == s[j-1]:dp[i][j] = dp[i][j-1] + dp[i-1][j-1]else:dp[i][j] = dp[i][j-1]return dp[-1][-1]- ??? 時間復雜度：O(n^2)
- ??? 空間復雜度：O(n)
1. 確定dp數組的含義
dp[i][j]：以i-1為結尾的s子序列中出現以j-1為結尾的t的個數為dp[i][j]。
2. 確定遞推公式
- s[i - 1] 與 t[j - 1]相等
- s[i - 1] 與 t[j - 1] 不相等
當s[i - 1] 與 t[j - 1]相等時，dp[i][j]可以有兩部分組成。
一部分是用s[i - 1]來匹配，那么個數為dp[i - 1][j - 1]。即不需要考慮當前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
3. dp數組初始化
初始化t的第一個字符對應的子字符串數量。
4. 確定遍歷順序
遞推公式中的j是i和j之前的元素下標，所以從前往后遞推。
5. 舉例
)
