打印最长的回文子串（LPS）

Question

我正在为自己学习DP，我可以轻松解决最长回文子串的长度，但很难真正打印最长回文子串。我检查了一个视频链接，他展示了一种获得LPS的方法，但我无法让它适用于更长的序列。考虑geeksforgeeks的例子：

S: forgeeksskeegfor

现在在我的方法中，我将填充表格的底部三角形，如下所示：

for (int i = 1; i < dp.length; ++i)
    for (int j = i-1; j >= 0; --i)
        dp[i][j] = (s[i] == s[j]) ? 2+dp[i-1][j+1] : Math.max(dp[i][j+1], dp[i-1][j])

因此，对于上述字符串，我的DP表如下所示：

      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
      f  o  r  g  e  e  k  s  s  k  e  e  g  f  o  r
 0 f  1
 1 o  1  1
 2 r  1  1  1
 3 g  1  1  1  1
 4 e  1  1  1  1  1
 5 e  2  2  2  2  2  1
 6 k  2  2  2  2  2  1  1
 7 s  2  2  2  2  2  1  1  1
 8 s  2  2  2  2  2  2  2  2  1
 9 k  4  4  4  4  4  4  4  2  1  1
10 e  6  6  6  6  6  6  4  2  1  1  1
11 e  8  8  8  8  8  6  4  2  2  2  2  1
12 g 10 10 10 10  8  6  4  2  2  2  2  1  1
13 f 12 10 10 10  8  6  4  2  2  2  2  1  1  1
14 o 12 12 10 10  8  6  4  2  2  2  2  1  1  1  1
15 r 12 12 12 10  8  6  4  2  2  2  2  1  1  1  1  1

这是视频中原始矩阵的转置，反过来，我不需要单独处理len 1,2，

12 => dp[15][0] => s[0] != s[15], now which way I go... I the video he goes on max of the next or top elements but for longer strings those might be equal. So, let's suppose I go upwards and nor 'f' neither 'r' are part of the LPS.
12 => dp[14][0] => s[0] != s[14]
12 => dp[13][0] => s[0] == s[13] => LPS: f[..........]f (At this point I go diagonally)
10 => dp[12][1] => s[1] != s[12] At this point I would start to go up as before but if I do that I won't get the LPS, so I have to go right
10 => dp[12][2] => s[2] != s[12] Still going right
10 => dp[12][3] => s[3] == s[12] => LPS: fg[........]gf
 8 => dp[11][4] => s[4] == s[11] => LPS: fge[......]efg
 6 => dp[10][5] => s[5] == s[10] => LPS: fgee[....]eefg
 4 => dp[ 9][6] => s[6] == s[ 9] => LPS: fgeek[..]keegf
 2 => dp[ 8][7] => s[7] == s[ 8] => LPS: fgeeksskeegf
 0 DONE

所以问题是，为什么我在dp[13][0]找到一个匹配项后，就把方向从向上切换到向上？如果我开始向右走，我发现我匹配，我不能继续向右走，也不能根据单元格的最大值来决定，因为它们可能相等。对于短字符串，请确保其工作原理与链接视频中的示例相同，但仅此而已。更长的字符串等于相邻单元格，那么我该走哪条路？

Answer 1

为了在DP中执行回溯，您需要记住您来自哪里。通常这意味着内存现在将增加到O（N^2），即使您可以在O（N）中完成。

我们从[12][1]到[12][2]而不是[11][2]的原因是，如果你在进行计算，[12][1]的值将由[12][2]确定，因为字母不相等，它是最大值。这就是我们向右转的原因——是细胞决定了这个细胞值。在所有其他情况下，这并不重要，因为这些值是相等的，所以你可以向右或向上移动。