poj 1159dp 메모

제목: 최소한의 문자를 추가하여 메모 문자열로 만들기

 1 #include<cstdio>

 2 #include<iostream>

 3 #include<algorithm>

 4 #include<cstring>

 5 #include<cmath>

 6 #include<queue>

 7 using namespace std;

 8 const int maxn=5001;

 9 int n,m,t;

10 short dp[maxn][maxn];

11 char s[maxn];

12 int main()

13 {

14     int i,j,k;

15     #ifndef ONLINE_JUDGE

16     freopen("1.in","r",stdin);

17     #endif

18         int len=0;

19         scanf("%d",&len);

20         scanf("%s",s);

21         for(i=0;i<len;i++)  dp[i][i]=0;

22         for(k=1;k<len;k++)

23         {

24             for(i=0;i+k<=len;i++)

25             {

26                 int j=k+i;

27                 if(s[i]==s[j])  dp[i][j]=dp[i+1][j-1];

28                 else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;

29             }

30         }

31         printf("%d
",dp[0][len-1]);

32     return 0;

33 }