C - 动态规划 - 编辑距离

以下是一个使用动态规划解决编辑距离问题的示例代码：

def minDistance(word1, word2):
    m = len(word1)
    n = len(word2)

    # 创建一个二维数组来存储转移状态
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化边界条件
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(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(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1

    return dp[m][n]

# 测试示例
word1 = "horse"
word2 = "ros"
print(minDistance(word1, word2))  # 输出： 3

在上述代码中，我们使用了一个二维数组 dp 来存储编辑距离的转移状态。其中，dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。

首先，我们初始化边界条件，即 dp[i][0] = i 和 dp[0][j] = j，表示将一个字符串转化为空字符串所需的最少操作次数。

然后，我们使用两层循环来计算转移状态。如果 word1[i - 1] == word2[j - 1]，即当前字符相等，那么不需要进行操作，直接将 dp[i][j] 的值设置为 dp[i - 1][j - 1]。否则，我们需要考虑三种操作：替换、插入和删除。分别对应于 dp[i - 1][j - 1]、dp[i][j - 1] 和 dp[i - 1][j]，取最小值并加上一次操作。

最后，返回 dp[m][n]，即将 word1 转换为 word2 所需的最少操作次数。

在示例中，我们将字符串 "horse" 转换为字符串 "ros"，最少需要 3 次操作，因此输出为 3。