LeetCode-Hot100-多维动态规划

前言

题单LeetCode 热题 100的多维动态规划部分，给出解析。

62. Unique Paths

题目描述

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

1 2	Input: m = 3, n = 7 Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

解题方法

这是一个经典的动态规划问题，要求计算从左上角到右下角的唯一路径数。机器人每次只能向右或向下移动，所以我们可以使用动态规划来解决这个问题。

思路：

设 dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的唯一路径数。
我们可以推导出，只有从左边的格子 (i, j-1) 或上面的格子 (i-1, j) 移动到 (i, j)，所以状态转移方程为：$$dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]$$
初始条件是：对于第一行和第一列，因为机器人只能一直向右或一直向下走，所以路径数都为1：
- dp[0][j] = 1 （第一行每个格子只能从左边来）
- dp[i][0] = 1 （第一列每个格子只能从上面来）
最后返回 dp[m-1][n-1]，即为到达右下角的路径数。

为了优化空间复杂度，我们可以使用空间压缩的技巧。因为在动态规划中，每次计算 dp[i][j] 只依赖于 dp[i-1][j]（当前列的上方）和 dp[i][j-1]（当前列的左方），因此我们可以只用一个一维数组来存储每一列的状态，反复更新这一列中的值，而不需要使用一个完整的二维数组。

优化思路：

使用一维数组 dp 来保存当前行的路径数。
对于每个位置 (i, j)，更新 dp[j] 的值为 dp[j] + dp[j-1]，其中 dp[j] 是上一行相同列的值，而 dp[j-1] 是当前行左边的值。

代码实现

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 创建一个大小为 m x n 的 dp 数组
        dp = [[1] * n for _ in range(m)]
        
        # 填充 dp 数组
        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]

优化空间复杂度：

def uniquePaths(m: int, n: int) -> int:
    # 创建一个大小为 n 的 dp 数组，初始值为 1
    dp = [1] * n
    
    # 从第二行开始计算
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j-1]
    
    # 返回 dp[n-1]，即为最终到达右下角的路径数
    return dp[-1]

复杂度分析

时间复杂度：$O(m×n)$，因为我们仍然需要遍历每一个格子。

空间复杂度：$O(m×n)$ 到 $O(n)$，只需要存储当前行的路径数。

64. Minimum Path Sum

原题链接

题目描述

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

1
2
3

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

1 2	Input: grid = [[1,2,3],[4,5,6]] Output: 12

Constraints:

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

解题方法

要解决这个问题，我们可以使用动态规划 (Dynamic Programming, DP) 来计算最小路径和。

思路：

设 dp[i][j] 表示到达坐标 (i, j) 时的最小路径和。
初始条件：dp[0][0] = grid[0][0]，表示从起点到起点的路径和就是起点的值。
递推关系：
- 对于第一行的格子，只能从左边过来，因此有：dp[0][j] = dp[0][j-1] + grid[0][j]。
- 对于第一列的格子，只能从上边过来，因此有：dp[i][0] = dp[i-1][0] + grid[i][0]。
- 对于其它格子，可以从左边或者上边到达，因此有：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
最终，dp[m-1][n-1] 就是从左上角到右下角的最小路径和。

为了优化空间复杂度，我们可以注意到在填充 dp 表时，只需要用到当前行和上一行的数据。因此，可以只使用一个一维数组 dp 来代替二维数组，这样可以将空间复杂度从 O(m × n) 优化到 O(n)。

优化思路：

使用一个长度为 n 的一维数组 dp，该数组会存储当前行的最小路径和。
遍历每一行时，更新 dp[j] 表示当前格子 (i, j) 的最小路径和。
每次更新 dp[j] 时，dp[j] 是从左边 dp[j-1] 或者从上边 dp[j] 更新而来，因此只需要保存当前行的状态。

要实现原地动态规划（In-Place DP），我们可以直接在输入的 grid 上进行修改，而不再需要额外的 dp 数组。通过不断更新 grid 中的元素为到达该位置的最小路径和，我们就可以实现空间复杂度为 O(1) 的解法。

思路：

初始条件：grid[0][0] 就是起点的值，不需要修改。
第一行只能从左边移动过来，所以 grid[0][j] = grid[0][j-1] + grid[0][j]。
第一列只能从上边移动过来，所以 grid[i][0] = grid[i-1][0] + grid[i][0]。
对于其他位置 grid[i][j]，可以从上边或者左边移动过来，取两者中的最小值再加上当前格子的值：grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]。
最终的答案将保存在 grid[m-1][n-1]，即右下角的位置。

代码实现

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 创建与 grid 同样大小的 DP 表
        dp = [[0] * n for _ in range(m)]
        
        # 初始化起点
        dp[0][0] = grid[0][0]
        
        # 初始化第一行
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        
        # 初始化第一列
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        
        # 填充整个 dp 表
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        
        # 返回右下角的值
        return dp[m-1][n-1]

优化后：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 使用长度为 n 的一维 DP 数组
        dp = [0] * n
        
        # 初始化第一行
        dp[0] = grid[0][0]
        for j in range(1, n):
            dp[j] = dp[j-1] + grid[0][j]
        
        # 从第二行开始，逐行更新 DP 数组
        for i in range(1, m):
            # 更新当前行的第一个元素
            dp[0] += grid[i][0]
            
            # 更新当前行的其他元素
            for j in range(1, n):
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        
        # 返回 dp[n-1] 即为最后一格的最小路径和
        return dp[-1]

原地dp：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 更新第一行
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]
        
        # 更新第一列
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        
        # 更新其余位置
        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]

复杂度分析

时间复杂度：$O(m×n)$

空间复杂度：$O(m×n)$ 到 $O(n)$ 到 $O(1)$。

5. Longest Palindromic Substring

原题链接

题目描述

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1 2	Input: s = "cbbd" Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

解题方法

动态规划

使用 动态规划 方法来求解最长回文子串问题。动态规划的核心思想是通过缓存子问题的结果，减少重复计算，从而提高效率。

动态规划解法思路：

定义状态：
- 用二维数组 dp，其中 dp[i][j] 表示子串 s[i:j+1] 是否是回文串。
状态转移：
- 初始化：所有长度为 1 的子串都是回文串，dp[i][i] = True。
- 如果 s[i] == s[j] 且 dp[i+1][j-1] == True，则 dp[i][j] = True，即 s[i:j+1] 是回文串。
- 否则，dp[i][j] = False。
计算过程：
- 遍历所有可能的子串长度，从小到大计算每个子串是否是回文。
- 如果 dp[i][j] 为 True，则更新当前最长回文子串。

中心扩展法

可以通过动态规划或中心扩展法来解决这个问题。这里我们使用 中心扩展法，它的时间复杂度为 $O(n^2)$，适用于给定字符串的长度不超过 1000 的情况。

中心扩展法思路：

中心扩展法：一个回文串可以通过其中心进行扩展。对于每一个字符位置（或两个字符之间的位置），我们尝试扩展出一个回文串，并记录下最长的回文串。
- 每个字符可以作为回文的中心，有两种情况：
  - 以一个字符为中心（奇数长度回文）。
  - 以两个字符为中心（偶数长度回文）。
步骤：
- 对每个字符（或者字符对）进行扩展，查找它们作为回文中心时的最长回文。
- 记录并返回最长的回文串。

代码实现

动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""

        # dp[i][j] 表示子串 s[i:j+1] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        
        # 初始化：所有长度为1的子串都是回文串
        for i in range(n):
            dp[i][i] = True
        
        start = 0  # 用来记录最长回文子串的起始位置
        max_len = 1  # 最长回文串的长度
        
        # 处理长度大于1的子串
        for length in range(2, n + 1):  # 子串长度从2到n
            for i in range(n - length + 1):
                j = i + length - 1  # 子串的右边界
                
                if s[i] == s[j]:  # 如果左右字符相等
                    if length == 2:  # 如果长度为2，且两个字符相等
                        dp[i][j] = True
                    else:  # 如果长度大于2，检查中间部分是否是回文
                        dp[i][j] = dp[i + 1][j - 1]
                    
                    # 更新最长回文子串的起始位置和长度
                    if dp[i][j] and length > max_len:
                        start = i
                        max_len = length
        
        return s[start:start + max_len]

中心扩展法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        def expandAroundCenter(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]

        longest = ""
        for i in range(len(s)):
            # 以s[i]为中心扩展
            odd_palindrome = expandAroundCenter(i, i)
            # 以s[i]和s[i+1]为中心扩展
            even_palindrome = expandAroundCenter(i, i + 1)
            
            # 取更长的回文串
            longest = max(longest, odd_palindrome, even_palindrome, key=len)
        
        return longest

复杂度分析

方法	时间复杂度	空间复杂度
动态规划	$O(n^2)$，其中 $n$ 是字符串的长度。我们遍历每个子串并进行状态转移。	$O(n^2)$，因为我们使用了一个二维数组 $dp$ 来记录所有子串的回文状态。
中心扩展法	$O(n^2)$，其中 $n$ 是字符串的长度。对于每个字符，我们扩展回文的过程中最多需要 $O(n)$ 次操作。	$O(1)$，因为只使用了常数的额外空间。

1143. Longest Common Subsequence

原题链接

题目描述

Given two strings text1 and text2, return the length of their longest common subsequence . If there is no common subsequence , return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

1
2
3

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

1
2
3

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

1
2
3

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

解题方法

这个问题是典型的动态规划问题，可以通过建立一个二维数组 dp 来解决。dp[i][j] 表示文本 text1 的前 i 个字符和文本 text2 的前 j 个字符的最长公共子序列的长度。

解题思路：

状态定义：
- dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。
状态转移：
- 如果 text1[i-1] == text2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1，即如果当前字符相等，那么最长公共子序列的长度是前面两个字符串的最长公共子序列加上当前的字符。
- 如果 text1[i-1] != text2[j-1]，那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即最长公共子序列要么来自 text1[0..i-2] 和 text2[0..j-1]，要么来自 text1[0..i-1] 和 text2[0..j-2]，取二者中的最大值。
初始化：
- dp[0][j] = 0，表示 text1 为空时，任何 text2 的子序列都没有公共部分。
- dp[i][0] = 0，表示 text2 为空时，任何 text1 的子序列都没有公共部分。
最终答案：
- 最终的答案是 dp[len(text1)][len(text2)]，即两个字符串的最长公共子序列的长度。

代码实现

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        # 创建一个二维数组 dp
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 填充 dp 数组
        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  # 当前字符相等，公共子序列长度加1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 当前字符不等，取最大值

        # 返回最终结果
        return dp[m][n]

复杂度分析

时间复杂度： $O(m × n)$，其中 $m$ 和 $n$ 分别是 text1 和 text2 的长度。

空间复杂度： $O(m × n)$，用于存储 dp 数组。

72. Edit Distance

原题链接

题目描述

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.

解题方法

要解决这个问题，我们可以使用动态规划。这是一个经典的编辑距离（Edit Distance）问题，常用的算法是Levenshtein Distance。我们可以通过动态规划计算将 word1 转换为 word2 所需的最少操作次数。

动态规划思路：
定义 dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 所需的最少操作数。基本的转移方程如下：

如果 word1[i-1] == word2[j-1]，则无需操作，dp[i][j] = dp[i-1][j-1]。
如果 word1[i-1] != word2[j-1]，则需要通过以下三种操作之一进行转换：
- 插入操作：将 word2[j-1] 插入到 word1[0..i-1] 中，因此 dp[i][j] = dp[i][j-1] + 1。
- 删除操作：删除 word1[i-1]，因此 dp[i][j] = dp[i-1][j] + 1。
- 替换操作：将 word1[i-1] 替换为 word2[j-1]，因此 dp[i][j] = dp[i-1][j-1] + 1。
  初始条件：

dp[0][j] = j，即将空字符串转换为 word2[0..j-1]，需要 j 次插入操作。
dp[i][0] = i，即将 word1[0..i-1] 转换为空字符串，需 i 次删除操作。

我们注意到在填充动态规划表格时，每次只需要当前行和前一行的值。因此，我们可以通过只保留两行 dp 数组来减少空间复杂度，从 O(m * n) 优化到 O(n)，其中 n 是 word2 的长度。

优化思路：
在计算 dp[i][j] 时，只依赖于 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1]。因此，我们可以使用两个一维数组：

prev：表示上一行的状态，即 dp[i-1][j]。
curr：表示当前行的状态，即 dp[i][j]。
每次处理完一行后，将 curr 赋值给 prev，并重新初始化 curr，这样只用两个长度为 n+1 的数组即可完成计算。

代码实现

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
    
        # dp数组，大小为 (m+1) x (n+1)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 初始化第一行和第一列
        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j
        
        # 填充dp数组
        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
        
        # 返回dp表的右下角的值
        return dp[m][n]

解释：

dp[i][j] 存储从 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数。
最终的结果就是 dp[m][n]，其中 m 和 n 分别是 word1 和 word2 的长度。

优化后：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        
        # 优化空间：只需要两行dp数组
        prev = list(range(n + 1))
        curr = [0] * (n + 1)
        
        for i in range(1, m + 1):
            curr[0] = i  # 当前行的第一列，代表把word1前i个字符变为空字符串
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = min(prev[j],    # 删除
                                curr[j - 1], # 插入
                                prev[j - 1]  # 替换
                                ) + 1
            # 将当前行赋值给prev，进行下一轮迭代
            prev, curr = curr, prev
        
        # 最终结果在prev[n]中
        return prev[n]

复杂度分析

时间复杂度：$O(m * n)$，其中 m 和 n 分别是 word1 和 word2 的长度。
空间复杂度：$O(m * n)$，因为需要一个大小为 (m+1) x (n+1) 的 dp 数组。优化后为 $O(n)$，因为我们只用到了两个长度为 n+1 的数组。