一、题目二、做题思路2.1 状态表示核心基础本题要求统计字符串中回文子串的总数。定义dp[i][j]表示子串s[i..j]包含两端是否为回文串true表示是false表示否。该二维表可覆盖所有连续子串。2.2 状态转移方程关键难点判断s[i..j]是否为回文串需满足两个条件首尾字符相等s[i] s[j]内部子串s[i1..j-1]为回文串或子串长度小于等于 2此时无需检查内部。因此转移为dp[i][j] (s[i] s[j]) (i1 j-1 ? true : dp[i1][j-1])即当i1 j-1长度 ≤ 2时直接为true否则依赖dp[i1][j-1]。2.3 初始化边界防护所有dp[i][j]初始化为false。长度 1 的子串i j必然回文会在递推中被正确置true因为首尾相同且内部为空。2.4 填表顺序递推方向dp[i][j]依赖dp[i1][j-1]左下位置因此从下到上i从n-1到0且内层从左到右j从i到n-1确保dp[i1][j-1]已计算。2.5 返回值目标映射遍历所有dp[i][j]每当为true时计数器ret最终返回ret即为回文子串总数。三、代码class Solution { public: int countSubstrings(string s) { int n s.size(); // 1. 创建dp表 // dp[i][j] 表示子串 s[i..j] 是否是回文串i j // 初始化为 false vectorvectorbool dp(n, vectorbool(n, false)); int ret 0; // 记录回文子串的总数 // 2. 填表顺序从下往上i 从 n-1 到 0从左往右j 从 i 到 n-1 // 因为 dp[i][j] 依赖于 dp[i1][j-1]更短的内部子串 // 所以需要先计算行号更大的 dp即 i 递减方向遍历。 for (int i n - 1; i 0; i--) { for (int j i; j n; j) { // 3. 状态转移方程 // 若 s[i] s[j]则 s[i..j] 是否为回文取决于内部子串 s[i1..j-1] 是否为回文 // 但当 i1 j-1即长度 ≤ 2时直接判定为 true。 if (s[i] s[j]) { dp[i][j] (i 1 j) ? dp[i 1][j - 1] : true; } // 若 s[i] ! s[j]dp[i][j] 保持 false已默认 // 4. 若当前子串是回文累加计数 if (dp[i][j] true) { ret; } } } // 5. 返回值回文子串的总个数 return ret; } };四、流程图五、题目六、做题思路6.1 状态表示核心基础本题要求返回最长的回文子串。定义dp[i][j]表示子串s[i..j]包含两端是否为回文串true表示是false表示否。通过二维表覆盖所有连续子串便于记录最长结果。6.2 状态转移方程关键难点判断s[i..j]是否为回文需满足首尾字符相等s[i] s[j]若子串长度 ≤ 2即i1 j则直接为true否则需内部子串s[i1..j-1]也为回文即dp[i1][j-1] true。因此转移为dp[i][j] (s[i] s[j]) (i1 j ? true : dp[i1][j-1])。6.3 初始化边界防护所有dp[i][j]初始化为false。长度 1 的子串i j会在递推中因首尾相同且长度≤2被置为true。6.4 填表顺序递推方向dp[i][j]依赖dp[i1][j-1]左下位置因此从下到上i从n-1到0内层从左到右j从i到n-1确保内部子串已先计算。6.5 返回值目标映射在遍历过程中每当dp[i][j] true且当前长度j-i1大于已记录的最长长度len时更新len和起始下标begin。最终返回s.substr(begin, len)即最长回文子串。七、代码class Solution { public: string longestPalindrome(string s) { int n s.size(); // 1. 创建dp表 // dp[i][j] 表示子串 s[i..j] 是否为回文串i j // 初始化为 false表示默认不是回文 vectorvectorbool dp(n, vectorbool(n, false)); int len 1; // 当前最长回文子串的长度 int begin 0; // 当前最长回文子串的起始下标 // 2. 填表顺序从下往上i 从 n-1 到 0从左往右j 从 i 到 n-1 // 因为 dp[i][j] 依赖于 dp[i1][j-1]更短的内部子串 // 所以需要先计算行号更大的 dp即 i 递减。 for (int i n - 1; i 0; i--) { for (int j i; j n; j) { // 3. 状态转移方程 // 只有当 s[i] s[j] 时才可能成为回文。 // 若子串长度 ≤ 2即 i1 j则直接判定为 true // 否则取决于内部子串 s[i1..j-1] 是否为回文。 if (s[i] s[j]) { dp[i][j] (i 1 j) ? dp[i 1][j - 1] : true; } // 若 s[i] ! s[j]dp[i][j] 保持 false // 4. 若当前子串是回文且长度大于已记录的最长长度则更新记录 if (dp[i][j] (j - i 1) len) { len j - i 1; begin i; } } } // 5. 返回值截取并返回最长回文子串 return s.substr(begin, len); } };八、流程图