力扣--动态规划/回溯算法131.分割回文串
思路分析：
- 动态规划 (DP)： 使用动态规划数组
dp，其中dp[i][j]表示从字符串s[i]到s[j]是否为回文子串。 - 预处理动态规划数组： 从字符串末尾开始，遍历每个字符组合，判断是否为回文子串，填充动态规划数组。
- 深度优先搜索 (DFS)： 利用递归，尝试从字符串的每个位置开始，生成满足回文子串条件的组合。
- 递归函数
dfs：- 接收参数：
dp为动态规划数组，s为原始字符串，start为当前递归的起始位置。 - 遍历当前可能的字符串，如果当前字符串是回文子串，则将其加入临时结果集
path。 - 如果当前位置
i达到字符串末尾，将当前路径加入结果集，并回溯。 - 继续递归生成组合，注意起始位置更新为
i + 1。 - 回溯过程中，撤销选择，继续尝试其他可能的组合。
- 接收参数：
- 主函数：
- 创建空的结果集
result和临时结果集path。 - 调用深度优先搜索函数
dfs，从起始位置0开始生成组合。 - 返回最终结果。
- 创建空的结果集
class Solution {// 存储最终结果的二维数组vector<vector<string>> result;// 存储当前正在生成的组合的临时结果vector<string> path;// 定义深度优先搜索函数，用于生成组合void dfs(vector<vector<bool>>& dp, string s, int start) {// 遍历当前可能的字符串for (int i = start; i < s.size(); i++) {// 如果当前字符串是回文子串if (dp[start][i]) {// 将当前回文子串加入临时结果集path.push_back(s.substr(start, i - start + 1));// 如果当前位置 i 达到字符串末尾，将当前路径加入结果集，并回溯if (i == s.size() - 1) {result.push_back(path);path.pop_back();return;}// 继续递归生成组合，注意起始位置更新为 i + 1dfs(dp, s, i + 1);// 回溯，撤销选择，继续尝试其他可能的组合path.pop_back();}}return;}public:// 主函数，生成所有回文子串的组合vector<vector<string>> partition(string s) {int n = s.size();// 二维动态规划数组，dp[i][j] 表示 s[i] 到 s[j] 是否为回文子串vector<vector<bool>> dp(n, vector<bool>(n, false));// 倒序遍历字符串，填充动态规划数组for (int i = n - 1; i >= 0; i--) {for (int j = i; j < n; j++) {// 如果当前字符相等，并且满足回文子串的条件if (s[i] == s[j] && (i == j || i == j - 1 || dp[i + 1][j - 1])) {dp[i][j] = true;}}}// 调用深度优先搜索函数 dfs，从起始位置 0 开始生成组合dfs(dp, s, 0);// 返回最终结果return result;}
};