回文串LeetCode5

根据dp回文串的转移公式,构建转移矩阵p

回文串LeetCode5

然而在调试的过程一直是出错 ,代码如下:

回文串LeetCode5

发现在矩阵的更新时 p并未有效更新,如下:

 

回文串LeetCode5

查看网上答案,发现只有第二个循环改成了 j=0;j<=i;j++   。这样就可以保证每一次循环的次数是叠加的,测试用例为“babad”

回文串LeetCode5

这里只列出i=2之前的,发现每次更新dp必须用到之前循环中的dp,按照这么理解,应该循环结构也可以这么写:

for(int i=len-1;i>=0;i--)

        for(int j=len-1;j>=i;j--)  保证不用到未更新的dp即可!