题解 | #最长回文串#

动态规划解决的遍历顺序

具体的动态规划的思想已经有很多小伙伴说过了，此处不再赘述。动态规划一定要注意遍历的顺序。

我们的动态规划转移方程为：dp[i][j] = dp[i+1][j-1]
所以更新dp[i][j]之前，一定要保证dp[i+1][j-1]已经被更新过了，是最新的值而不是原始值。具体来看代码：

如果你的遍历顺序是下面这样的：

...
for(int i = 0 ; i < n ; i++ ){//左边界
    for(int j = i ; j < n ; j++ ){//控制右边界
        ...
        flag[i][j] = flag[i+1][j-1];
        ...
     }
}

那么就踩雷了。你的遍历顺序是从左到右的遍历，在你遍历flag[i][j]时，flag[i+1][j-1]还没有被更新，所以，即便flag[i+1][j-1]本应该是回文，但是因为还没有被遍历到，此时依旧为原始值false，那么flag[i][j]也为false，最后得不到正确的答案。所以我们在遍历flag[i][j]时，需要已经遍历过flag[i+1][j-1]才可以。具体的遍历顺序如下所示。

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        if(n < 2) return n;

        boolean[][] flag = new boolean[n][n]; //动态规划
        int maxLen = 1; // 存储最长的回文长度

        for(int i = 0 ; i < n ; i++) flag[i][i] = true; //对角线赋值为真

        for(int i = n - 1 ; i >= 0 ; i-- ){//控制左边界
            for(int j = n - 1 ; j > i ; j-- ){//控制右边界

                //只有一个字母已经赋值为真，两端不同flag[i][j]不可能为回文
                if(i - j == 0 || A.charAt(i) != A.charAt(j)) continue; 

                //两端相同，且为两个字母，一定为回文
                if(j - i < 2) flag[i][j] = true;

                //两端相同，此时应该使用状态转移方程
                //在更新flag[i][j]之前应该先保证flag[i+1][j-1]已被更新过而非原始值
                else flag[i][j] = flag[i+1][j-1];

                //更新最长长度
                if(flag[i][j]) maxLen = Math.max(maxLen , j - i + 1);
            }
        }
        return maxLen;
    }
}