91、不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

思路解答：

1. 初始化 dp 数组，将第一行和第一列的值都设为 1，因为机器人只能向右或向下移动，所以第一行和第一列的位置只有一种到达方式。
2. 对于其他位置 dp$[i][j]$，可以从上方位置 dp$[i-1][j]$ 或左方位置 dp$[i][j-1]$ 到达，因此有 dp$[i][j]$ = dp$[i-1][j]$ + dp$[i][j-1]$。
3. 最终返回 dp$[m-1][n-1]$，即到达右下角的不同路径数。

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

92、最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

思路解答：

dp$[i][j]$ 表示从左上角到达网格的第 i 行、第 j 列位置的最小路径和。

1. 初始化 dp 数组，将第一行和第一列的值分别累积计算，因为在这两条边上，路径只能沿着一条直线移动，所以到达每个位置的最小路径和就是前一个位置的最小路径和加上当前位置的值。
2. 对于其他位置 dp$[i][j]$，可以从上方位置 dp$[i-1][j]$ 或左方位置 dp$[i][j-1]$ 到达，选择路径和较小的那个作为当前位置的最小路径和，即 dp$[i][j]$ = min(dp$[i-1][j]$, dp$[i][j-1]$) + grid$[i][j]$。
3. 最终返回 dp$[m-1][n-1]$，即从左上角到达右下角的最小路径和。

def  minminPathSum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])

    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]

    for j in range(1, n):
        grid[0][j] += grid[0][j - 1]

    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

    return grid[m - 1][n - 1]

93、最小回文字符串

给你一个字符串 s，找到 s 中最长的回文子串，如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路解答:

dp$[i][j]$ 表示从索引 i 到 j 的子串是否为回文子串。

1. 初始化 dp 数组，将所有长度为 1 的子串都标记为回文子串（即 dp$[i][i]$ = True）。
2. 对于长度大于 1 的子串，遍历所有可能的子串长度和起始索引，更新 dp 数组。
3. 在更新 dp 数组时，如果 s[i] == s[j] 且 dp$[i+1][j-1]$ 是回文子串（即 i 和 j 之间的子串是回文串），则 dp$[i][j]$ 也是回文子串。
4. 记录最长的回文子串的起始索引和长度，最终返回该子串。

def  minminCut(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_length = 1

    # 单个字符一定是回文串
    for i in range(n):
        dp[i][i] = True

    # 遍历所有可能的子串长度和起始索引
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2 and s[i] == s[j]:
                dp[i][j] = True
            elif s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
            if dp[i][j] and length > max_length:
                start = i
                max_length = length

    return s[start:start + max_length]

94、最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

思路解答：

dp$[i][j]$ 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度。

1. 初始化一个 (m+1) x (n+1) 的二维数组 dp，其中 m 和 n 分别是 text1 和 text2 的长度。
2. 对于 dp 数组的边界情况，即当 i=0 或 j=0 时，最长公共子序列的长度为 0。
3. 对于其他情况，如果 text1[i-1] 等于 text2[j-1]，说明当前字符可以作为最长公共子序列的一部分，此时 dp$[i][j]$ = dp$[i-1][j-1]$ + 1。
4. 如果 text1[i-1] 不等于 text2[j-1]，则最长公共子序列的长度为 max(dp$[i-1][j]$, dp$[i][j-1]$)，即取删除 text1[i-1] 或 text2[j-1] 后的最长公共子序列的长度。
5. 最终返回 dp$[m][n]$，即 text1 和 text2 的最长公共子序列的长度。

def  longestCommonSubsequence(text1: str, text2: str) -> int:

    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

95、编辑距离

给你两个单词 word1 和 word2， 请返回将 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')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

思路解答：

dp$[i][j]$ 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。

1. 初始化一个 (m+1) x (n+1) 的二维数组 dp，其中 m 和 n 分别是 word1 和 word2 的长度。
2. 对于 dp 数组的边界情况，当 i=0 时，表示将一个空字符串转换成 word2 的前 j 个字符需要插入 j 次操作；当 j=0 时，表示将 word1 的前 i 个字符转换成一个空字符串需要删除 i 次操作。
3. 对于其他情况，分为三种情况：
   • 如果 word1[i-1] 等于 word2[j-1]，则不需要进行操作，dp$[i][j]$ = dp$[i-1][j-1]$。
   • 如果 word1[i-1] 不等于 word2[j-1]，则可以进行插入、删除或替换操作，取这三种操作的最小值加一，即 dp[i][j] = min(dp$[i-1][j]$, dp$[i][j-1]$, dp$[i-1][j-1]$) + 1。
4. 最终返回 dp$[m][n]$，即将 word1 转换成 word2 所需要的最少操作数。

def minminDistance(word1: str, word2: str) -> int:
    m, n = len(word1), 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    return dp[m][n]