题意描述：给一个字符串s，每次删除其中的一个回文substring，问多少次删完？
本题并没有特别明显的套路特征。第二类区间型DP应该是穷尽其他想法之后的兜底方案。我们定义dp[i:j]表示对于s[i:j]最少需要删几次。接下来考虑，如何将这个大区间转化为小区间呢？如果没有其他明显的特征的话，一个常见的处理方法就是看最后一个元素s[j]。
因为无论怎么设计方案，s[j]都可以是最后一个被删除的。我们就想s[j]会和谁一起删除？必然是找相同的字符。因此我们在[i:j]中寻找一个s[k]==s[j]，那么原来的大区间就分化为了两部分：dp[i][k-1]+dp[k][j]。而对于后者，我们发现s[k]和s[j]并不占用操作，而是可以和删除dp[k+1][j-1]的时候一起消除（回文加了一层而已）。
因此状态转移方程是：
for (int len = 1; len <= N; len++)
for (int i = 1; i+len-1<=N; i++)
{
int j = i+len-1;
dp[i][j] = dp[i][j-1]+1;
for (int k=i; k<j; k++)
{
if (arr[k]==arr[j])
dp[i][j] = min(dp[i][j], dp[i][k-1]+max(1,dp[k+1][j-1]));
}
}特别注意，删除s[k]和s[j]并不是永远都不占用操作数，如果当dp[k+1][j-1]本身是0的时候，我们还是需要将s[k]和s[j]当作一对紧挨着的回文数删去的。