例题：Educational Codeforces Round 61 (Rated for Div. 2) F题

题目链接：http://codeforces.com/contest/1132/problem/F

题目大意：

给你一个只含小写字母的字符串，每次只能删除一段含有一样字母的区间，问最少删多少次，才能删除整个字符串

解题思路：

（第一次做区间dp  所以记录详细点  适合新手）

我们用dp[ i ][ j ]代表把区间 i 到 j 完全删除需要的次数

状态转移方程

  1. if(s[ i ] == s[ j ])  dp[ i ][ j ] = dp[i+1][j-1]+1;  (两头一样，我们把中间的消去，只剩下两头了，再消一次就好了)
  2. if(s[ i ] != s[ j ])  dp[ i ][ j ] =min(dp[ i+1 ][ j ],dp[ i ][ j-1 ])+1;（两头不一样，左端单独消去或者右端单独消去）
  3. 枚举区间i，j中的点，dp[ i ][ j ] = min(dp[ i ][ j ],dp[ i ][ k ] + dp[ k ][ j ] - 1);

前两个状态呢，比较容易得到，但是这两个状态只解决了一半的问题。

我们先来看如何实现这两个状态，首先，我们做dp，根据dp数组的意义，

  1. 所有 i > j 的dp值为0（区间在 i < x < j ）
  2. 当i = j 时，dp[ i ][ j ]=1（区间内就一个数）

如图 5X5

而根据刚才初步推出来的状态转移方程，我们知道dp[ i ][ j ]要么等于黄色格子+1，要么等于两个蓝色格子最小值+1；

所以，我们根据已知条件和状态转移方程就可以把dp数组填满

当然  我们得要斜着填 如下图  （因为每一个dp值是由其左下方、左边、下边、的值得到的）

    //斜着遍历
    for(int c=1;c<n;c++){//共n-1轮
        for(int i=1,j=c+1;i<=n&&j<=n;i++,j++){
                //i代表行 j代表列
            }
        }
    }

好，那么这是前两个状态转移，看似解决了问题，但是还有一种特殊情况没被解决；

比如：  abaca    

根据我们的状态转移方程2  第一个和第五个字符一样，所以dp[ 1 ][ 5 ] = dp[ 2 ][ 4 ] +1=4

但是其实答案是3（用两步消掉 b c ，一步消除所有的a）

为了解决这种状态，我们在区间i j内枚举每一个点为k，dp[ i ][ j ] = min(dp[ i ][ j ],dp[ i ][ k ] + dp[ k ][ j ] - 1);

正常的话 dp[ i ][ j ] 是等于 dp[ i ][ k ] + dp[ k ][ j ] - 1的  如  abc  或 aba

但是当 特殊情况时  如 aaa  那么dp[ i ][ k ] + dp[ k ][ j ] - 1  得到的值是小于dp[ i ][ j ]的，才是答案。

AC代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1e3+7;
int dp[maxn][maxn];
char s[maxn];
int n;
int main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)dp[i][i]=1;

    for(int c=1;c<n;c++){
        for(int i=1,j=c+1;i<=n&&j<=n;i++,j++){
            if(s[i]==s[j])dp[i][j]=dp[i+1][j-1]+1;
            else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]-1);
            }
        }
    }
    printf("%d\n",dp[1][n]);
    return 0;
}