python-最优包含

解题思路:

动态规划。

①创建一个大小为(n+1)*(m+1)的二维数组，命名为dp，n和m分别为字符串s、t的长度。

   其中dp[i][j]表示s中的前i个字符要想包含t的前j个字符最少需要修改几次。

②dp[i][0] = 0（i = 0 to n）

③状态转移方程

   当s[i] = t[j]时，这时我们不用进行变换则，dp[i][j] = dp[i-1][j-1]

   当s[i] != t[j]时，这时有两种情况，一种情况是，在s中没取到第i个字符时，已经可以包含t取到字符j了。

                                                       另一种情况是，此时t取到第j个字符时还未被包含，那么在此时，就要进行一次变换

   所以dp[i][j] = min(dp[i-1][j]，dp[i-1][j-1]+1)

注意事项:

参考代码:

from cmath import inf    
    
    
s = input().strip()    
t = input().strip()    
n = len(s)    
m = len(t)    
    
dp = [[inf for j in range(m+1)] for i in range(n+1)]  
for i in range(n+1):  
    dp[i][0] = 0  
      
for i in range(1,n+1):    
    for j in range(1,m+1):    
        if s[i-1] == t[j-1]:    
            dp[i][j] = dp[i-1][j-1]    
        else:    
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1)    
print(dp[n][m])