LeetCode 热题 100 | (第二部分多维动态规划)

1 5. 最长回文子串

核心理念：将整体问题划分为多个局部问题。

• 整体问题：判断从第 i 个字符至第 j 个字符是否构成回文
• 局部问题：判断从第 i + 1 个字符至第 j - 1 个字符是否构成回文、第 i 个字符与第 j 个字符是否相等
• 整体问题 = 局部问题 1 + 局部问题 2

思路解析图：如图所示，若要确认“从第 i 个字符至第 j 个字符是否构成回文”，需同时满足两个前提条件，即“从第 i + 1 个字符至第 j - 1 个字符构成回文”以及“第 i 个字符与第 j 个字符相等”。

很自然地会考虑构建一个二维的 dp 数组，其中 dp[i][j] 用于表示从第 i 个字符至第 j 个字符之间构成的字符串是否为回文结构。若满足回文条件，则将 dp[i][j] 设定为 1；反之，设定为 0。

在初始阶段，可能会采用如下方式编写循环结构：

 for (int i = 0; i < n; ++i) {

    
     for (int j = i; j < n; ++j) {
    
     dp[i][j] = dp[i