动态规划进阶：回文串与双数组问题的深度剖析与实战指南

动态规划（DP）是算法面试中的常客，其中回文串问题和两个数组的DP问题更是高频考点。本文将以通俗易懂的方式，结合TypeScript、C++、JavaScript、Python、Go等主流语言的最佳实践，带你从原理到代码，彻底掌握这两类问题。

回文串问题：从子串到最长子串

回文串问题核心在于如何高效判断子串是否为回文。暴力枚举时间复杂度高达O(n³)，而动态规划可以将复杂度降至O(n²)。

回文子串的DP表示

定义dp[i][j]表示字符串从索引i到j的子串是否为回文串。状态转移方程如下：

• 基础情况：单个字符i == j时，dp[i][j] = true。
• 相邻字符：j - i == 1时，若s[i] == s[j]，则为回文。
• 一般情况：s[i] == s[j] && dp[i+1][j-1]。

⚠️ 注意事项：遍历顺序必须从下往上、从左到右，因为dp[i][j]依赖dp[i+1][j-1]（左下角的值）。同时，由于i <= j，我们只需填充DP表的上三角部分。

下图清晰展示了DP表的填充顺序（图片来源：算法可视化工具）。

对应的代码实现（以Python为例）：

class Solution {
    public int countSubstrings(String s) {
        int n=s.length();
        boolean[][] f=new boolean[n][n];
        f[0][0]=true;
        int count=0;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<=n-1;j++){
               if(s.charAt(i)!=s.charAt(j)){
                f[i][j]=false;
               }else{
                if(i==j){
                    f[i][j]=true;
                    count++;
                }else if(i+1==j){
                    f[i][j]=true;
                    count++;
                }else{
                    f[i][j]=f[i+1][j-1];
                    if(f[i][j]==true){
                        count++;
                    }
                }
               }
            }
        }
        return count;
    }
}

最长回文子串

在回文子串计数的基础上，我们只需额外记录最长回文子串的起始位置和长度。在更新dp[i][j]为true时，若当前长度j - i + 1大于已知最大长度，则更新记录。

✅ 这一技巧同样适用于Go、C++、TypeScript等语言，只需注意字符串索引和边界条件。

class Solution {
    public String longestPalindrome(String s) {
        int n=s.length();
        boolean[][] f=new boolean[n][n];
        f[0][0]=true;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<=n-1;j++){
                if(s.charAt(i)!=s.charAt(j)){
                    f[i][j]=false;
                }else{
                    if(i==j){
                        f[i][j]=true;
                    }else if(i+1==j){
                        f[i][j]=true;
                    }else{
                        f[i][j]=f[i+1][j-1];
                    }
                }
            }
        }
        //走到这里 统计f表每行 为true的距离相差的最大
        int max=0;
        int begin=0;
        for(int i=0;i<=n-1;i++){
            for(int j=i;j<=n-1;j++){
                if(f[i][j]&&(j-i+1)>max){
                    max=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+max);
    }
}

[AFFILIATE_SLOT_1]

两个数组的DP问题：最长公共子序列与编辑距离

当问题涉及两个字符串或数组时，DP表通常定义为二维：dp[i][j]表示第一个序列的前i个元素与第二个序列的前j个元素的最优解。

最长公共子序列（LCS）

LCS问题要求找出两个字符串中最长的公共子序列（不要求连续）。状态转移：

• 若s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始化技巧：通常将dp[0][j]和dp[i][0]置为0，表示空序列的公共子序列长度为0。在JavaScript和TypeScript中，可以使用Array.from或嵌套循环初始化二维数组。

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int m=s1.length();
        int n=s2.length();
        int[][] f=new int[m+1][n+1];
        s1=" "+s1;
        s2=" "+s2;
        int max=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1.charAt(i)==s2.charAt(j)){
                    f[i][j]=f[i-1][j-1]+1;
                    max=Math.max(f[i][j],max);
                }else{
                    f[i][j]=Math.max(f[i][j-1],f[i-1][j]);
                    max=Math.max(f[i][j],max);
                }
            }
        }
        return max;
    }
}

✂️ 编辑距离（Levenshtein Distance）

编辑距离计算将一个字符串转换为另一个字符串所需的最少操作次数（插入、删除、替换）。状态转移：

• 初始化：dp[i][0] = i（删除所有字符），dp[0][j] = j（插入所有字符）。
• 若s1[i-1] == s2[j-1]，则dp[i][j] = dp[i-1][j-1]。
• 否则，dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])。

⚠️ 初始化注意事项：与LCS类似，但初始值不再是0，而是与索引相关的数值。在C++或Go中，注意使用min函数或手动比较。

class Solution {
    public int minDistance(String s1, String s2) {
        int m=s1.length();
        int n=s2.length();
        int[][] f=new int[m+1][n+1];
        //初始化
        for(int j=0;j<=n;j++){
            f[0][j]=j;
        }
         for(int i=0;i<=m;i++){
            f[i][0]=i;
        }
        s1=" "+s1;
        s2=" "+s2;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1.charAt(i)==s2.charAt(j)){
                    f[i][j]=f[i-1][j-1];
                }else{
                    f[i][j]=Math.min(f[i-1][j-1]+1,Math.min(f[i][j-1]+1,f[i-1][j]+1));
                }
            }
        }
        return f[m][n];
    }
}

[AFFILIATE_SLOT_2]

总结与最佳实践

本文深入剖析了回文串和双数组动态规划问题的核心思路与代码实现。关键要点：

• 回文串问题：DP表只填上三角，遍历顺序从下往上、从左到右。
• 双数组问题：注意初始化边界值，LCS用0，编辑距离用索引值。
• 语言无关：上述思路适用于TypeScript、C++、JavaScript、Python、Go等所有主流语言，只需注意语法差异。

建议读者在LeetCode上练习相关题目（如5、1143、72），并结合可视化工具加深理解。掌握这些模式，你将能轻松应对大部分字符串DP面试题。