LeetCode每日一题系列的学习目标

前言
编辑距离，作为典型的动态规划类问题，出现在leetcode72题中，被归类为难度较高的题目。编辑距离问题的核心挑战在于如何合理地设计状态转移的方式以及做出相应的选择。在下文中，我们将逐步展开分析，以应对与编辑距离相关的各类问题。

文章结构概述

• 问题说明

  • 解题思路解析

  • 初始代码实现

  • 动态规划方法改进

  • leetcode 运行结果展示

  • • 动态规划表
    • 基于递归与记忆化的方法

  • 拓展内容

  • 总结归纳

题目描述

给定两个字符串 word1 与 word2，要求计算将 word1 转化为 word2 所需的最少操作次数。
对于一个字符串，允许执行以下三种操作：

• 在任意位置插入一个字符
• 删除任意一个字符
• 将某个字符替换为另一个字符

示例1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解析：
horse -> rorse（将 ‘h’ 替换为 ‘r’）
rorse -