LC115不同的子序列（未掌握）
- 遞推公式與LC392類似，但是初始化略有不同
- LC392的dp數組含義為相同字符個數
- 而本體的dp數組含義為出現的次數，因此dp[i][0]=1
- 兩種情況
- s[i-1]==t[j-1]
- dp[i][j] = dp[i-1][j-1]
- dp[i][j] = dp[i-1][j]
- s[i-1]!=t[j-1]=》dp[i][j] = dp[i-1][j]
- 代碼
LC583兩個字符串的刪除操作
- 其實本質就是求最長公共子序列，跟LC1143一樣
- 代碼
- 方法二：
- dp[i][j]：以i-1為結尾的字符串word1，和以j-1位結尾的字符串word2，想要達到相等，所需要刪除元素的最少次數。
- 遞推公式：
- 當word1[i - 1] == word2[j - 1]：dp[i][j] = dp[i - 1][j - 1];
- 當word1[i - 1] ！= word2[j - 1]
- 刪word1[i - 1]，最少操作次數為dp[i - 1][j] + 1
- 刪word2[j - 1]，最少操作次數為dp[i][j - 1] + 1
- 同時刪word1[i - 1]和word2[j - 1]，操作的最少次數為dp[i - 1][j - 1] + 2
- 但是dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，當 同時刪word1[i - 1]和word2[j - 1]，dp[i][j-1] 本來就不考慮 word2[j - 1]了，那么我在刪 word1[i - 1]，是不是就達到兩個元素都刪除的效果，即 dp[i][j-1] + 1
- 代碼
LC72 編輯距離（未掌握）
- dp[i][j] 表示以下標i-1為結尾的字符串word1，和以下標j-1為結尾的字符串word2，最近編輯距離為dp[i][j]。
- 遞推公式：
- 當word1[i - 1] == word2[j - 1]：dp[i][j] = dp[i - 1][j - 1];
- 當word1[i - 1] ！= word2[j - 1]
- 刪除word1[i - 1]=》dp[i][j] = dp[i - 1][j] + 1;
- 刪除word2[j - 1]=》dp[i][j] = dp[i ][j-1] + 1;
- 增加：因為增加可以任意增加一個元素，增加元素就類似與刪除元素，長為x和長為y的比較，如果需要增加一定是一個比另外一個長，那可以加一個也就可以用減一個元素替代
- 替換：將word1[i - 1]替換為word2[j- 1]=》dp[i][j] = dp[i - 1][j - 1]+1;
- 代碼
