leetcode刷题指南之PalindromePartitioningII

题目分析

给一个字符串s，问最少切几下使得切出的子串都是回文串。比如，s=,那么只要切一下变成[,]就可以。

。。。。。。。。。。。

咳咳，

继续解题

解题思路

先从简单情况考虑起，如果s本身就是一个回文串，那么答案显然是0。 如果s不是回文串，那至少要切一下。

考虑切的第一块，即包含第一个字母的那一块。这个时候我们可能会想到贪心取最长的一个，但贪心是不对的，考虑一个例子：，如果第一个贪心的话，最远可以切到，需要两下，++,一共两下，但是我们可以切成+，即只需要一下。

因此我们去枚举第一个切分的位置，我们就得到了一个回文串，和剩下的子串，对于剩下的子串又是一个相同的问题：最少要切多少下？因此，我们就得到了一个更小的子问题，也就是动态规划的标志。

令dp[i]代表[0,i]要最少切多少下才能满足条件，枚举前面切分的位置j,那么dp[i]=min(dp[i],dp[j-1]+1)，当然，子串(i,j)要是一个回文串。

下面以作为例子：

代码示例

作者：东大ACM退役队伍

编辑：刘凯旋