UVA1351-----String Compression-----区间DP（记忆化搜索实现）

我是按照他的想法，算法是自己实现的
给一个字符串，可以把连续相同的部分进行缩写成k(S)的形式，S是一个字符串，k表示有连续相同的S
例如，abgogogogo，可以缩写成ab4(go). 还可以嵌套缩写，比如
“nowletsgogogoletsgogogo”， 缩写成“now2(lets3(go))”
 
思路：
一道区间dp，但是这题并不好想
f(i, j)表示字符串的i~j位的最小位数
那么
f(i, j) = min{
                  min{ f(i,k)+f(k+1, j), i<=k<j }，
                  min{ digitNum(k)+f[l][l+k-1]+2, 如果字符串可以由前k个字符串重复组成的 }
                }
digitNum(k)表示数字k的位数
判断区间（i, j）是否有由连续ｋ个组成的字符串连续组成的，直接用Ｏ(n)的时间判断
 
区间DP用记忆画搜索比较容易实现，不用仔细去想迭代的写法
所以以后写区间DP就可以用记忆化搜索的写法
代码：
#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<string.h>  
  
using namespace std;  
  
const int maxn = 300;  
int dp[maxn][maxn];  
char s[maxn];  
const int INF = 0x3f3f3f3f;  
  
bool check(int l,int r,int k)  
{  
    int i;  
    int len = r-l+1;  
    i=0;  
    while(i<k)  
    {  
        int p;  
        for(p=1;l+p*k+i<=r;p++)  
        {  
            if(s[l+i] != s[l+p*k+i])  
                return false;  
        }  
        i++;  
    }  
  
    return true;  
}  
  
int min(int a,int b)  
{  
    return a<b?a:b;  
}  
  
int digitnum(int k)  
{  
    int len = 0;  
    while(k>0)  
    {  
        len++;  
        k/=10;  
    }  
    return len;  
}  
  
int DP(int l,int r)  
{  
    if(dp[l][r] != -1)  
        return dp[l][r];  
      
    int len = r-l+1;  
    int d;  
      
    dp[l][r] = INF;  
  
    for(int k=l;k<r;k++)  
        dp[l][r] = min(dp[l][r],DP(l,k)+DP(k+1,r));  
  
    for(d=1;d<=len/2;d++)  
    {  
        if(len%d != 0)  
            continue;  
        if(check(l,r,d))  
        {  
            dp[l][r] = min(dp[l][r],digitnum(len/d)+DP(l,l+d-1)+2);  
        }  
    }  
      
    return dp[l][r];  
}  
  
int main()  
{  
    int t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%s",s);  
        memset(dp,-1,sizeof(dp));  
        int len = strlen(s);  
        int i;  
        for(i=0;i<len;i++)  
            dp[i][i] = 1;  
        cout<<DP(0,len-1)<<endl;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,