115.不同的子序列
class Solution(object):def numDistinct(self, s, t):""":type s: str:type t: str:rtype: int"""dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]for i in range(len(s)):dp[i][0]=1for j in range(1, len(t)):dp[0][j]=0for 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] + dp[i-1][j]else:dp[i][j]=dp[i-1][j]return dp[-1][-1]
583. 两个字符串的删除操作
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""dp=[[0]*(len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0]=ifor j in range(len(word2)+1):dp[0][j]=jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+1):if word1[i-1]==word2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+2)return dp[-1][-1]
72. 编辑距离
- 题目链接：72. 编辑距离
- 下标j-1 操作的是j-2
- 增删换各自的表示方式
class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""dp =[[0]*(len(word2)+1) for _ in range(len(word1)+1)]for i in range(len(word1)+1):dp[i][0]=ifor j in range(len(word2)+1):dp[0][j]=jfor i in range(1, len(word1)+1):for j in range(1, len(word2)+1):if word1[i-1]==word2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1return dp[-1][-1]
