hot100多维动态规划题解

发表于 2025/01/21 更新于 2025/01/21

作者 匆匆那年 32 分钟阅读

62. 不同路径

问题描述

一个机器人位于一个 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 * 10^9$

题解

这道题目可以通过动态规划（Dynamic Programming, DP）来求解，或者通过组合数学的方法。我们使用动态规划的方法来解决，下面是题解：

动态规划方法

我们可以定义一个二维的 DP 数组 dp，其中 dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的不同路径的数量。

状态转移：

从当前位置 (i, j) 来看，机器人可以选择从左边 (i, j-1) 或者从上面 (i-1, j) 来：
- 如果从上面来，路径数为 dp[i-1][j]。
- 如果从左边来，路径数为 dp[i][j-1]。

因此，状态转移公式是：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件：

dp[0][0] = 1，即起点只有一种路径。
第一行和第一列只有一种路径，因为机器人只能一直向右或者一直向下。

最终结果：

dp[m-1][n-1] 就是最终答案，即从左上角到右下角的不同路径数量。

C++ 代码实现

  
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    // 创建一个 m * n 的 DP 数组
    vector<vector<int>> dp(m, vector<int>(n, 0));

    // 初始化起点
    dp[0][0] = 1;

    // 填充 DP 数组
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 && j == 0) continue;  // 跳过起点
            if (i > 0) dp[i][j] += dp[i - 1][j];  // 从上方来
            if (j > 0) dp[i][j] += dp[i][j - 1];  // 从左方来
        }
    }

    // 返回右下角的路径数
    return dp[m - 1][n - 1];
}

解释：

我们首先创建一个 m x n 的二维数组 dp，初始化为 0。
设置 dp[0][0] = 1，代表起点只有一种路径。
然后通过双重循环遍历每个位置 (i, j)：
- 如果当前坐标不是起点 (0, 0)，则 dp[i][j] 可以通过 dp[i-1][j]（从上方来）和 dp[i][j-1]（从左方来）累加得来。
最终返回 dp[m-1][n-1] 即为右下角的路径数。

时间复杂度：

时间复杂度是 O(m * n)，其中 m 是行数，n 是列数。因为我们需要遍历整个 m x n 的二维数组。

空间复杂度：

空间复杂度是 O(m * n)，因为我们使用了一个二维 DP 数组。

优化：

如果只是关心最终结果，可以优化空间复杂度，将 DP 数组减少为一维数组。

  
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);  // 只需要一维数组

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] += dp[j - 1];  // dp[j] 代表从左边和上面过来的路径数
        }
    }

    return dp[n - 1];  // 返回右下角的路径数
}

这个优化版本使用了 O(n) 的空间复杂度。

64. 最小路径和

问题描述

给定一个包含非负整数的 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]，表示从起点 (0, 0) 到达位置 (i, j) 的最小路径和。

状态转移：

对于每个位置 (i, j)，机器人可以选择从上面 (i-1, j) 或者从左边 (i, j-1) 移动到当前位置。
因此，dp[i][j] 就是 grid[i][j]加上从上面或左边到达当前位置的最小值：
1 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
对于第一行和第一列，它们只能从一个方向来（分别是从左边或从上边），因此需要单独处理。

边界条件：

dp[0][0] = grid[0][0]，起点的路径和就是网格中的值。

最终结果：

dp[m-1][n-1] 就是我们要求的最小路径和。

C++ 代码实现

  
#include <vector>
#include <algorithm>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    // 创建一个 DP 数组
    vector<vector<int>> dp(m, vector<int>(n, 0));

    // 初始化起点
    dp[0][0] = grid[0][0];

    // 填充第一列
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // 填充第一行
    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // 填充剩余的 DP 数组
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 返回右下角的最小路径和
    return dp[m - 1][n - 1];
}

解释：

我们首先初始化一个 dp 数组，大小与 grid 相同。
设置 dp[0][0] = grid[0][0]，即起点的最小路径和。
填充第一列和第一行：
- 第一列只能从上面到达，因此每个位置的值是上一个位置的路径和加上当前格子的值。
- 第一行只能从左边到达，因此每个位置的值是左边位置的路径和加上当前格子的值。
填充剩余的 dp 数组，对于每个位置 (i, j)，路径和是当前位置的值加上从上面或左边到达该位置的最小值。
最后返回 dp[m-1][n-1]，即右下角的最小路径和。

时间复杂度：

时间复杂度是 O(m * n)，其中 m 是行数，n 是列数，因为我们需要遍历整个 m x n 的网格。

空间复杂度：

空间复杂度是 O(m * n)，因为我们使用了一个二维数组 dp 来存储每个位置的最小路径和。

优化空间复杂度：

如果只关心当前行和上一行的值，可以将二维 dp 数组优化为一维数组。每次更新一行的值时，我们只需要保存上一行的信息。

  
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    // 创建一个一维 DP 数组
    vector<int> dp(n, 0);

    // 初始化第一列
    dp[0] = grid[0][0];
    for (int j = 1; j < n; ++j) {
        dp[j] = dp[j - 1] + grid[0][j];
    }

    // 从第二行开始更新 DP 数组
    for (int i = 1; i < m; ++i) {
        dp[0] += grid[i][0];  // 第一列的特殊处理
        for (int j = 1; j < n; ++j) {
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1]);
        }
    }

    // 返回右下角的最小路径和
    return dp[n - 1];
}

优化后空间复杂度：

空间复杂度是 O(n)，仅使用了一维数组。

2. 最长回文子串

问题描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

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

示例 2：

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

提示：

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

题解

这道题目是经典的字符串问题，要求找到字符串中的最长回文子串。解决方法有多种，这里介绍两种常见的解决方法：中心扩展法 和 动态规划法。

方法 1: 中心扩展法

回文字符串的特点是对称的，因此我们可以从每个字符开始，向左右两边扩展，检查是否是回文。每次扩展时，我们将当前回文子串的长度与已知的最大长度进行比较，并更新最大长度。

思路：

对于每个字符 s[i]，将其作为回文的中心进行扩展，考虑两种情况：
- 回文的中心是一个字符（奇数长度回文）。
- 回文的中心是两个字符之间（偶数长度回文）。
对于每个中心，向左右两边扩展，直到不能扩展为止。
在扩展过程中，记录最大回文的起始位置和长度。

时间复杂度：

时间复杂度是 O(n^2)，其中 n 是字符串的长度。对于每个字符，我们最多扩展 O(n) 次。
空间复杂度是 O(1)，只需要常数空间来记录最大回文子串的起始位置和长度。

C++ 代码实现

  
#include <string>
using namespace std;

string longestPalindrome(string s) {
    if (s.empty()) return "";

    int start = 0, maxLen = 1;

    // 中心扩展法
    for (int i = 0; i < s.size(); ++i) {
        // 处理奇数长度的回文
        int len1 = expandAroundCenter(s, i, i);
        // 处理偶数长度的回文
        int len2 = expandAroundCenter(s, i, i + 1);

        // 找到最大回文长度
        int len = max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }

    return s.substr(start, maxLen);
}

// 扩展中心
int expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        --left;
        ++right;
    }
    return right - left - 1;  // 返回回文长度
}

解释：

我们遍历字符串中的每个字符，分别作为奇数和偶数长度回文的中心。
对于每个中心，使用 expandAroundCenter 函数向左右扩展，直到不能扩展为止，返回回文的长度。
更新最大回文子串的起始位置和长度，最后通过 substr 获取最长回文子串。

方法 2: 动态规划法

动态规划方法的思路是构建一个二维 DP 数组 dp[i][j]，表示子串 s[i..j] 是否是回文。通过填充这个 DP 数组来找出最长回文子串。

思路：

对于每个子串 s[i..j]，如果 s[i] == s[j] 且 s[i+1..j-1] 是回文，则 s[i..j] 是回文。
初始化时，所有长度为 1 的子串都是回文，长度为 2 的子串如果 s[i] == s[i+1]，也是回文。
对于更长的子串，利用状态转移方程进行填充。

时间复杂度：

时间复杂度是 O(n^2)，空间复杂度是 O(n^2)，需要构建一个 n x n 的 DP 数组。

C++ 代码实现

  
#include <string>
#include <vector>
using namespace std;

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, maxLen = 1;

    // 所有长度为1的子串都是回文
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
    }

    // 检查长度为2的子串
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }

    // 检查长度大于2的子串
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i < n - len + 1; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (len > maxLen) {
                    maxLen = len;
                    start = i;
                }
            }
        }
    }

    return s.substr(start, maxLen);
}

解释：

我们创建一个二维 DP 数组 dp[i][j]，表示子串 s[i..j] 是否为回文。
初始化时，所有长度为 1 的子串是回文，长度为 2 的子串如果两个字符相同，则是回文。
对于长度大于 2 的子串，通过 dp[i+1][j-1] 来判断是否是回文。
在填充 DP 数组的过程中，记录最长回文子串的起始位置和长度。

总结：

中心扩展法 时间复杂度较低，空间复杂度较小，适合解决此类问题。
动态规划法 更直观，但空间复杂度较高，适合对空间不太敏感的情况。

对于这道题目，中心扩展法 更为常见，且通常性能更好。

1143. 最长公共子序列

问题描述

给定两个字符串 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 仅由小写英文字符组成。

题解

这道题目是经典的 最长公共子序列（Longest Common Subsequence, LCS）问题。我们可以使用 动态规划 来高效地求解该问题。

思路

假设有两个字符串 text1 和 text2，我们定义一个二维数组 dp，其中 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，表示当前字符匹配时，最长公共子序列长度加 1。
如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示当前字符不匹配时，取前一个状态中的最大值。

边界条件：

dp[0][j] = 0，表示 text1 的长度为 0 时，最长公共子序列的长度为 0。
dp[i][0] = 0，表示 text2 的长度为 0 时，最长公共子序列的长度为 0。

最终，dp[m][n] 即为 text1 和 text2 的最长公共子序列的长度，其中 m 和 n 分别是 text1 和 text2 的长度。

C++ 代码实现

  
#include <vector>
#include <string>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();

    // 创建 DP 数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 填充 DP 数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            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];
}

解释：

创建一个 (m+1) x (n+1) 的二维 DP 数组，m 和 n 分别是 text1 和 text2 的长度。
初始化 dp[0][*] 和 dp[*][0] 为 0，表示空字符串和任意字符串的最长公共子序列长度为 0。
使用嵌套循环填充 dp 数组，依次比较 text1[i-1] 和 text2[j-1]，如果相等，则 dp[i][j] 加 1，否则取 dp[i-1][j] 和 dp[i][j-1] 中的最大值。
最终返回 dp[m][n]，即为 text1 和 text2 的最长公共子序列长度。

时间复杂度：

时间复杂度是 O(m * n)，其中 m 和 n 分别是 text1 和 text2 的长度。我们需要填充一个 m x n 的 DP 数组。

空间复杂度：

空间复杂度是 O(m * n)，因为我们使用了一个二维数组 dp 来存储子问题的解。

优化空间复杂度：

如果只关心当前行和上一行的 DP 状态，可以将二维数组优化为一维数组，空间复杂度优化为 O(n)。

  
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();

    // 创建一维 DP 数组
    vector<int> dp(n + 1, 0);

    // 填充 DP 数组
    for (int i = 1; i <= m; ++i) {
        int prev = 0;
        for (int j = 1; j <= n; ++j) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = prev + 1;  // 当前字符匹配，长度加 1
            } else {
                dp[j] = max(dp[j], dp[j - 1]);  // 当前字符不匹配，取前一个状态中的最大值
            }
            prev = temp;
        }
    }

    // 返回最长公共子序列的长度
    return dp[n];
}

优化后的空间复杂度：

空间复杂度是 O(n)，我们只使用了一个大小为 n + 1 的一维数组。

总结：

动态规划法 是解决这个问题的标准方法，时间复杂度为 O(m * n)，空间复杂度可以优化为 O(n)。

72. 编辑距离

问题描述

给你两个单词 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 由小写英文字母组成

题解

这道题是经典的 编辑距离（Edit Distance）问题，我们可以使用 动态规划 来高效地解决。

思路

我们可以定义一个二维数组 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]，即不需要操作。
否则，我们有三种操作可以选择：
1. 插入操作：将 word2[j-1] 插入到 word1[i-1]，即 dp[i][j] = dp[i][j-1] + 1。
2. 删除操作：删除 word1[i-1]，即 dp[i][j] = dp[i-1][j] + 1。
3. 替换操作：将 word1[i-1] 替换为 word2[j-1]，即 dp[i][j] = dp[i-1][j-1] + 1。

最终，dp[m][n] 就是将 word1 转换为 word2 的最小操作数，其中 m 和 n 分别是 word1 和 word2 的长度。

边界条件：

dp[i][0] = i，表示将 word1[0..i-1] 转换为空字符串，操作数为 i（需要进行 i 次删除操作）。
dp[0][j] = j，表示将空字符串转换为 word2[0..j-1]，操作数为 j（需要进行 j 次插入操作）。

C++ 代码实现

  
#include <vector>
#include <string>
using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();

    // 创建 DP 数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 初始化边界条件
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;  // 将 word1[0..i-1] 转换为空字符串
    }
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = j;  // 将空字符串转换为 word2[0..j-1]
    }

    // 填充 DP 数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            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 - 1][j], dp[i][j - 1]}) + 1;  // 选择三种操作中最小的
            }
        }
    }

    return dp[m][n];  // 返回最终结果
}

解释：

初始化：我们首先初始化边界条件，dp[i][0] = i 和 dp[0][j] = j，表示将一个字符串转换为空字符串所需的操作数。
填充 DP 数组
：我们通过嵌套循环，依次计算每个 dp[i][j] 的值：
- 如果当前字符 word1[i-1] 和 word2[j-1] 相同，则不需要操作，dp[i][j] = dp[i-1][j-1]。
- 否则，我们计算三种操作的最小值，dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1，分别代表替换、删除和插入操作。
返回结果：最终 dp[m][n] 就是将 word1 转换为 word2 的最小操作数。

时间复杂度：

时间复杂度是 O(m * n)，其中 m 和 n 分别是 word1 和 word2 的长度。我们需要填充一个大小为 m x n 的 DP 数组。

空间复杂度：

空间复杂度是 O(m * n)，因为我们使用了一个二维 DP 数组来存储中间结果。

空间优化：

如果我们只关心当前行和上一行的 DP 状态，可以将二维数组优化为两行一维数组，空间复杂度优化为 O(min(m, n))。

优化后的 C++ 代码

  
int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();

    // 确保 m <= n，减少空间
    if (m > n) return minDistance(word2, word1);

    vector<int> dp(n + 1, 0);
    for (int i = 0; i <= m; ++i) {
        vector<int> prev(dp);
        for (int j = 1; j <= n; ++j) {
            if (i == 0) {
                dp[j] = j;  // 初始化边界条件
            } else {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = prev[j - 1];  // 字符相同，不需要操作
                } else {
                    dp[j] = min({prev[j - 1], prev[j], dp[j - 1]}) + 1;  // 选择三种操作中最小的
                }
            }
        }
    }

    return dp[n];  // 返回最终结果
}

空间优化后的复杂度：

时间复杂度仍然是 O(m * n)。
空间复杂度优化为 O(min(m, n))。

总结：

这道题使用动态规划解决，核心思路是通过计算每一对字符的编辑距离，逐步得到最终结果。
时间复杂度是 O(m * n)，空间复杂度可以优化到 O(min(m, n))。

leetcode, hot100

本文由作者按照 CC BY 4.0 进行授权

62. 不同路径

问题描述

题解

动态规划方法

状态转移：

边界条件：

最终结果：

C++ 代码实现

解释：

时间复杂度：

空间复杂度：

优化：

64. 最小路径和

问题描述

题解

思路

状态转移：

边界条件：

最终结果：

C++ 代码实现

解释：

时间复杂度：

空间复杂度：

优化空间复杂度：

优化后空间复杂度：

2. 最长回文子串

问题描述

题解

方法 1: 中心扩展法

思路：

时间复杂度：

C++ 代码实现

解释：

方法 2: 动态规划法

思路：

时间复杂度：

C++ 代码实现

解释：

总结：

1143. 最长公共子序列

问题描述

题解

思路

状态转移：

边界条件：

C++ 代码实现

解释：

时间复杂度：

空间复杂度：

优化空间复杂度：

优化后的空间复杂度：

总结：

72. 编辑距离

问题描述

题解

思路

状态转移：

边界条件：

C++ 代码实现

解释：

时间复杂度：

空间复杂度：

空间优化：

优化后的 C++ 代码

空间优化后的复杂度：

总结：

热门标签