07.04.02-Exercises.md

07.04.02 练习题目（第 14 天）

1. 1143. 最长公共子序列

1.1 题目大意

描述：给定两个字符串 text1 和 text2。

要求：返回两个字符串的最长公共子序列的长度。如果不存在公共子序列，则返回 0。

说明：

• 子序列：原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
• 公共子序列：两个字符串所共同拥有的子序列。
• $1 \le text1.length, text2.length \le 1000$。
• text1 和 text2 仅由小写英文字符组成。

示例：

• 示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

• 示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

2. 0064. 最小路径和

2.1 题目大意

描述：给定一个包含非负整数的 $m \times n$ 大小的网格 grid。

要求：找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：

• 每次只能向下或者向右移动一步。
• $m == grid.length$。
• $n == grid[i].length$。
• $1 \le m, n \le 200$。
• $0 \le grid[i][j] \le 100$。

示例：

• 示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

• 示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

3. 0072. 编辑距离

3.1 题目大意

描述：给定两个单词 word1、word2。

对一个单词可以进行以下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

要求：计算出将 word1 转换为 word2 所使用的最少操作数。

说明：

• $0 \le word1.length, word2.length \le 500$。
• word1 和 word2 由小写英文字母组成

示例：

• 示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

• 示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

习题解析

1. 「1143. 最长公共子序列」习题解析：网页链接、Github 链接
2. 「0064. 最小路径和」习题解析：网页链接、Github 链接
3. 「0072. 编辑距离」习题解析：网页链接、Github 链接