005 - Longest Palindromic Substring 的 DP 再分析

之前的帖子提到了看到的帖子 都是通过如下公式来做 DP 的：
    dp[i, j] = 1                                   if i == j     同一个
             = s[i] == s[j]                        if j = i + 1  相邻
             = s[i] == s[j] && dp[i + 1][j - 1]    if j > i + 1  互为mirror

我自己的方法则不同，是把其中一个字符串反向了，换算坐标来匹配字符的，
匹配到了（相同字母）的格子则继承左上的值加一， （不同于上面的状态方程是依赖右下的值来置 1）
然后通过计算横纵坐标之差是不是就是填入的数字来得到正确的结果。

仔细再分析了一下它们的差异，也对这个状态方程理解得更清楚了一些。
对于前两种情况，比价容易理解，单独一个字符，或者两个字符相等且相邻，自然都构成回文。

对于第三种情况，实际上是，以对角线上的某个节点作为中心点，沿着垂直于对角线的方向（也就是反对角线）向两端延伸，
因此，可以如这个公式那样，写成（当 i，j 对应的字母相等时）一个格子的值，依赖于其左下的格子，
也可以写成（当 i，j 对应的字母相等时）一个格子的值，依赖于其右上的格子。
只不过前一种情况，是向右上延伸，后一种情况是向左下延伸而已。

而按照这里的状态方程，只需要处理 j > =i 的情况，或者 j <= i 的情况即可，也就是说，只需要计算半个矩阵就够了，
这点在实际跑的结果中也可以得到印证：我的 DP 跑出来是 460 ms，而处理半个矩阵的结果是 300 ms，少了三分之一。

另外，计算的过程也要注意：
按照上面的状态方程，后一个依赖的左下，也就是说，左下的值必须在当前格子之前计算出来，否则就错了。
所以，沿着这个方程，只能是在上半区纵向处理数据，这样才能保证被依赖的格子先计算出来，依赖的后计算出来。
而依赖的起点，要么是两个字符相邻，要么是两个下标指向同一个字符。

这样就有了下面的代码（来自一个博客）：

class Solution {
public:
    string longestPalindrome(string s) {
        int dp[s.size()][s.size()] = {0}, left = 0, right = 0, len = 0;
        for (int i = 0; i < s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
                if (dp[j][i] && len < i - j + 1) {
                    len = i - j + 1;
                    left = j;
                    right = i;
                }
            }
            dp[i][i] = 1;
        }
        return s.substr(left, right - left + 1);
    }
};

以字符串 abcddcba 为例，它的执行结果：

1 0 0 0 0 0 0 1 
  1 0 0 0 0 1 0
    1 0 0 1 0 0
      1 1 0 0 0
        1 0 0 0
          1 0 0
            1 0
              1

而事实上，也完全可以把它写成对右上的依赖，这样计算的过程就不需要一列一列地来了，而是按照习惯的一行一行的来就好了：

string longestPalindrome2(string s) {
    int dp[s.size()][s.size()]={0}, left = 0, right = 0, len = 0;
    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i][j] = (s[i] == s[j] && (i - j < 2 || dp[i - 1][j + 1])); //rely on R-U
            if (dp[i][j] && len < i - j + 1) {
                len = i - j + 1;
                left = j;
                right = i;
            }
        }
        dp[i][i] = 1;
    }
    return s.substr(left, right - left + 1);
}

它的执行结果：

1
0 1
0 0 1
0 0 0 1
0 0 0 1 1
0 0 1 0 0 1
0 1 0 0 0 0 1 
1 0 0 0 0 0 0 1

现在在回头去看自己的 DP，其实也是可以通过只处理一般，以及说明依赖关系。来减少冗余的计算的，
只不过因为横向的字符串反向了，计算的结果将出现在正向的对角线上，而不是上面的反向的对角线上。

好了，说到这里算是差不多说清楚了。