当前位置：首页 > news >正文

LeetCode-22day:多维动态规划

news 2025/8/27 9:47:15

多维动态规划经典题目总结（C++实现）

多维动态规划是动态规划的一种扩展，适用于更复杂的问题。本文总结了五道经典的多维动态规划问题，帮助你更好地理解和掌握多维动态规划的应用。

🟢 1. 不同路径（Unique Paths）

📄 题目描述：

一个机器人位于一个 m x n 网格的左上角，只能向下或向右移动。它试图到达网格的右下角。有多少种不同的路径可以到达？

🧠 解题思路（简洁版）

动态规划：
- f[j] 表示到达第 j 列的路径数。
- 状态转移：f[j] = f[j] + f[j - 1]。
- 初始化：第一行全为 1。

⏱️ 复杂度分析

时间复杂度：O(m × n)，其中 m 和 n 分别为行数和列数。
空间复杂度：O(n)，优化后的动态规划表。

✅ C++ 实现

class Solution {
public:int uniquePaths(int m, int n) {vector<int> f(n, 1);for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {f[j] += f[j - 1];}}return f[n - 1];}
};

🟢 2. 最小路径和（Minimum Path Sum）

📄 题目描述：

给定一个 m x n 的网格 grid，每个单元格包含一个非负整数，表示该单元格的代价。从左上角到右下角的路径，路径上的代价总和最小是多少？

🧠 解题思路（简洁版）

动态规划：
- dp[i][j] 表示到达 (i, j) 的最小路径和。
- 初始化第一行和第一列。
- 状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

⏱️ 复杂度分析

时间复杂度：O(m × n)，其中 m 和 n 分别为行数和列数。
空间复杂度：O(m × n)，动态规划表。

✅ C++ 实现

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {if (grid.size() == 0 || grid[0].size() == 0) return 0;int rows = grid.size(), columns = grid[0].size();vector<vector<int>> dp(rows, vector<int>(columns));dp[0][0] = grid[0][0];for (int i = 1; i < rows; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}for (int j = 1; j < columns; j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}for (int i = 1; i < rows; i++) {for (int j = 1; j < columns; j++) {dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}return dp[rows - 1][columns - 1];}
};

🟢 3. 最长回文子串（Longest Palindromic Substring）

📄 题目描述：

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

🧠 解题思路（简洁版）

动态规划：
- dp[i][j] 表示子串 ( s[i:j] ) 是否为回文。
- 初始化：单个字符是回文。
- 状态转移：若 ( s[i] = s[j] ) 且 ( j - i < 3 ) 或 ( dp[i+1][j-1] ) 为真，则 ( dp[i][j] ) 为真。
- 遍历所有可能的子串长度，更新最长回文子串的起始位置和长度。

⏱️ 复杂度分析

时间复杂度：O(n²)，其中 n 为字符串长度。
空间复杂度：O(n²)，动态规划表。

✅ C++ 实现

class Solution {
public:string longestPalindrome(string s) {int n = s.size();if (n < 2) return s;int maxLen = 1;int begin = 0;vector<vector<int>> dp(n, vector<int>(n));for (int i = 0; i < n; i++) dp[i][i] = true;for (int L = 2; L <= n; L++) {for (int i = 0; i < n; i++) {int j = L + i - 1;if (j >= n) break;if (s[i] != s[j]) {dp[i][j] = false;} else {if (j - i < 3) dp[i][j] = true;else dp[i][j] = dp[i + 1][j - 1];}if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substr(begin, maxLen);}
};

🟢 4. 最长公共子序列（Longest Common Subsequence）

📄 题目描述：

给定两个字符串 text1 和 text2，找到它们的最长公共子序列的长度。

🧠 解题思路（简洁版）

动态规划：
- dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。
- 状态转移：
  - 若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
  - 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
- 初始化：dp[i][0] = dp[0][j] = 0。

⏱️ 复杂度分析

时间复杂度：O(m × n)，其中 m 和 n 分别为两个字符串的长度。
空间复杂度：O(m × n)，动态规划表。

✅ C++ 实现

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.length(), n = text2.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int i = 1; i <= m; i++) {char c1 = text1.at(i - 1);for (int j = 1; j <= n; j++) {char c2 = text2.at(j - 1);if (c1 == c2) {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];}
};

🟢 5. 编辑距离（Edit Distance）

📄 题目描述：

给定两个字符串 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作次数。操作包括插入、删除和替换字符。

🧠 解题思路（简洁版）

动态规划：
- dp[i][j] 表示 word1 前 i 个字符和 word2 前 j 个字符的最小编辑距离。
- 状态转移：
  - 插入：dp[i][j-1] + 1
  - 删除：dp[i-1][j] + 1
  - 替换：dp[i-1][j-1] + (word1[i-1] != word2[j-1])
- 初始化：dp[i][0] = i，dp[0][j] = j。

⏱️ 复杂度分析

时间复杂度：O(m × n)，其中 m 和 n 分别为两个字符串的长度。
空间复杂度：O(m × n)，动态规划表。

✅ C++ 实现

class Solution {
public:int minDistance(string word1, string word2) {int n = word1.length();int m = word2.length();if (n * m == 0) return n + m;vector<vector<int>> dp(n + 1, vector<int>(m + 1));for (int i = 0; i < n + 1; i++) dp[i][0] = i;for (int j = 0; j < m + 1; j++) dp[0][j] = j;for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {int left = dp[i - 1][j] + 1;int down = dp[i][j - 1] + 1;int left_down = dp[i - 1][j - 1];if (word1[i - 1] != word2[j - 1]) left_down += 1;dp[i][j] = min(left, min(down, left_down));}}return dp[n][m];}
};

📌 总结

题目	方法	时间复杂度	空间复杂度
不同路径	动态规划	O(m × n)	O(n)
最小路径和	动态规划	O(m × n)	O(m × n)
最长回文子串	动态规划	O(n²)	O(n²)
最长公共子序列	动态规划	O(m × n)	O(m × n)
编辑距离	动态规划	O(m × n)	O(m × n)