模版题-动态规划-两个字符串的删除操作( 这种题目也是动态规划解决 )
- 版权声明：本站原创文章，于2026-06-08，由 管理员 发表。
- 转载请注明： 模版题-动态规划-两个字符串的删除操作( 这种题目也是动态规划解决 ) | CodeGarden
```python
class Solution:
# 给定两个单词word1和word2，返回使得word1和word2相同所需的最小步数。
# 每步可以删除任意一个字符串中的一个字符。
# 1 <= word1.length, word2.length <= 500
# word1 和 word2 只包含小写英文字母
def minDistance(self, word1: str, word2: str) -> int:
# 这种问题也是用动态规划解决
# dp[i][j]表示以word1[i-1]结尾和以word2[j-1]结尾的字符串相同所需的最小步数
n1 = len( word1 )
n2 = len( word2 )
if n1 == 0: return n2
if n2 == 0: return n1
dp = [ [ 0 for _ in range( n2 + 1 ) ] for _ in range( n1 + 1 ) ]
# 初始化
# dp[ 0 ][ j ]时 s = ""
# dp[ i ][ 0 ]时 s = ""
for j in range( n2 + 1 ): dp[ 0 ][ j ] = j
for i in range( n1 + 1 ): dp[ i ][ 0 ] = i
for i in range( 1, n1 + 1 ):
for j in range( 1, n2 + 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 ], dp[ i ][ j - 1 ] ) + 1
return dp[ n1 ][ n2 ]
```