力扣–动态规划/回溯算法131.分割回文串

思路分析：

1. 动态规划 (DP)： 使用动态规划数组 dp，其中 dp[i][j] 表示从字符串 s[i] 到 s[j] 是否为回文子串。
2. 预处理动态规划数组： 从字符串末尾开始，遍历每个字符组合，判断是否为回文子串，填充动态规划数组。
3. 深度优先搜索 (DFS)： 利用递归，尝试从字符串的每个位置开始，生成满足回文子串条件的组合。
4. 递归函数 dfs：
   • 接收参数：dp 为动态规划数组，s 为原始字符串，start 为当前递归的起始位置。
   • 遍历当前可能的字符串，如果当前字符串是回文子串，则将其加入临时结果集 path。
   • 如果当前位置 i 达到字符串末尾，将当前路径加入结果集，并回溯。
   • 继续递归生成组合，注意起始位置更新为 i + 1。
   • 回溯过程中，撤销选择，继续尝试其他可能的组合。
5. 主函数：
   • 创建空的结果集 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 + 1
                dfs(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;
    }
};