赞
踩
【代码随想录训练营】【Day 53】【动态规划-12】| Leetcode 115, 583, 72
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = 1
for i in range(1, m+1):
for j in range(1, n+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[m][n]
class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) # 0-i-1,0-j-1 的最小步数 dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1, m+1): dp[i][0] = i for j in range(1, n+1): dp[0][j] = j for i in range(1, m+1): for j in range(1, n+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(min(dp[i-1][j-1]+2, dp[i-1][j]+1), dp[i][j-1]+1) return dp[m][n]
class Solution: def minDistance(self, word1: str, word2: str) -> int: dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] for i in range(len(word1)+1): dp[i][0] = i for j in range(len(word2)+1): dp[0][j] = j for 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-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) return dp[len(word1)][len(word2)]
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。