回文串LeetCode5
根据dp回文串的转移公式,构建转移矩阵p
然而在调试的过程一直是出错 ,代码如下:
发现在矩阵的更新时 p并未有效更新,如下:
查看网上答案,发现只有第二个循环改成了 j=0;j<=i;j++ 。这样就可以保证每一次循环的次数是叠加的,测试用例为“babad”
这里只列出i=2之前的,发现每次更新dp必须用到之前循环中的dp,按照这么理解,应该循环结构也可以这么写:
for(int i=len-1;i>=0;i--)
for(int j=len-1;j>=i;j--) 保证不用到未更新的dp即可!