C 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2021-12-05

#include <stdio.h>

int main()
{
    char s[51];
    int dp[51][51]={[0 ... 50]={[0 ... 50]=100}};
    gets(s);
    int len = strlen(s);
    for(int length=1;length<=len;++length)
    {
        for(int l=0;l<len;++l)
        {
            int r = l+length-1;
            if(r > len)
                break;
            if(l == r)
            {
                dp[l][r]=1;
                continue;
            }
            if(s[l] == s[r])
                dp[l][r] = dp[l+1][r] < dp[l][r-1] ? dp[l+1][r] : dp[l][r-1];
            else
                for(int k=l;k<r;++k)
                    dp[l][r] = (dp[l][k]+dp[k+1][r]) < dp[l][r] ? (dp[l][k]+dp[k+1][r]) : dp[l][r];
        }
    }
    printf("%d",dp[0][len-1]);

    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2021-12-01

#include<stdio.h>
#include<string.h>
int min(int a,int b){
    return a<b?a:b;
}
int main()
{
    long long int n,m,i,j,b,c,d,k;
    char a[60];
    int dp[100][100]={0};
    scanf("%s",a);
    n=strlen(a);
    int right=n-1,left=0;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            if(i==j)dp[i][j]=1;
            else dp[i][j]=9999999;
        }
    }
    for(m=1;m<=n;m++){
        for(i=0;i+m<n;i++){
            if(a[i]==a[i+m]){
                dp[i][i+m]=min(dp[i+1][i+m],dp[i][i+m-1]);
            }
            else{
                for(k=i;k<=i+m-1;k++){
                    dp[i][i+m]=min(dp[i][i+m],dp[i][k]+dp[k+1][i+m]);
                }
            }
        }
    }
    printf("%d",dp[0][n-1]);
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 484KB, 提交时间: 2021-11-17

#include<iostream>
#include<string>
using namespace std;

int main(){
    string s;
    cin>>s;
    int n = s.length();
    int dp[n + 1][n] ;
    for(int i = 0; i < n;i++){
        dp[1][i] = 1;
        
    }
    
    
    for(int l = 2; l <= n;l++){
        for(int i = 0;i < n + 1 - l; i++){
            if(s[i] == s[i + l -1]){
                dp[l][i] = min(dp[l-1][i],dp[l-1][i+1]);}
            else{
                for(int k = 1; k < l;k++){
                    if(k == 1){dp[l][i] = dp[k][i] + dp[l - k][i + k];}
                    else{
                    dp[l][i] = min(dp[l][i],dp[k][i] + dp[l - k][i + k]);
                    }
                }
                
            }
        }
    }
    cout<<dp[n][0];

    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 340KB, 提交时间: 2022-06-22

#include <stdio.h>

int min(int a, int b) {
    return a > b ? b : a;
}

int main() {
    char str[51];
    int dp[51][51] = {[0 ... 50]={ [0 ... 50] = 51 }};
    scanf("%s", str);
    int sLen = strlen(str);
    
    for (int i = 0; i < sLen; i++) {
        dp[i][i] = 1;
    }
    for (int d = 1; d < sLen; d++) {
        for (int i = 0; i < sLen - d; i++) {
            if (str[i] == str[i+d]) {
                dp[i][i+d] = min(dp[i+1][i+d], dp[i][i+d-1]);
            } else {
                for (int k = 0; k < d; k++) {
                    dp[i][i+d] = min(dp[i][i+d], dp[i][i+k] + dp[i+k+1][i+d]);
                }
            }
        }
    }
    
    printf("%d", dp[0][sLen-1]);
    
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 344KB, 提交时间: 2022-05-08

#include <stdio.h>

int main() {
    char s[51];
    int d[51][51] = {[0 ... 50] = {[0 ... 50] = 100}};
    gets(s);
    int h = strlen(s);
    for (int length = 1; length <= h; ++length) {
        for (int l = 0; l < h; ++l) {
            int r = l + length - 1;
            if (r > h)
                break;
            if (l == r) {
                d[l][r] = 1;
                continue;
            }
            if (s[l] == s[r])
                d[l][r] = d[l + 1][r] < d[l][r - 1] ? d[l + 1][r] : d[l][r - 1];
            else
                for (int k = l; k < r; ++k)
                    d[l][r] = (d[l][k] + d[k + 1][r]) < d[l][r] ? (d[l][k] + d[k + 1][r]) : d[l][r];
        }
    }
    printf("%d", d[0][h- 1]);
    return 0;
}