Python3 解法, 执行用时: 63ms, 内存消耗: 4632K, 提交时间: 2023-05-12 21:04:28

if __name__ == '__main__':
    c=' '+input()
    n=len(c)-1
    f=[[0x3f3f3f3f]*(n+1) for i in range(n+1) ]
    for i in range(1,n+1):
        f[i][i]=1
    for lengh in range(1,n+1):
        for l in range(1,n-lengh+1):
            r=l+lengh
            if c[l]==c[r]:
                f[l][r]=min(min(f[l+1][r],f[l][r-1]),f[l][r])
            for i in range(l,r):
                f[l][r]=min(f[l][r],f[l][i]+f[i+1][r])
    print(f[1][n])

pypy3(pypy3.6.1) 解法, 执行用时: 85ms, 内存消耗: 20208K, 提交时间: 2020-08-20 13:43:58

#!/usr/bin/env python3
#
# [CQOI2007]涂色PAINT
#
import sys, os

s = input().strip()
n = len(s)

dp = [[float('inf')] * n for _ in range(n)]
for i in range(n): dp[i][i] = 1
for l in range(2, n + 1):
	for i in range(n - l + 1):
		j = i + l - 1
		if s[i] == s[j]:
			dp[i][j] = min(dp[i + 1][j], dp[i][j - 1])
		else:
			for k in range(i, j):
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k +1][j])

print(dp[0][n - 1])

C++ 解法, 执行用时: 3ms, 内存消耗: 624K, 提交时间: 2021-07-18 20:44:07

#include<bits/stdc++.h>
using namespace std;

char str[102],str1[102];
int dp[102][102];
int main()
{
	cin>>str1;
	int n=strlen(str1);
	strcpy(str+1,str1);
	for(int l=1;l<=n;l++){
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			dp[i][j]=dp[i+1][j]+1;
			for(int k=i+1;k<=j;k++)
			{
				if(str[k]==str[i])
					dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 4444K, 提交时间: 2019-06-12 20:23:20

#include<bits/stdc++.h>
using namespace std;
int main()
{
	char a[10086];
	scanf("%s",a);
	int dp[1005][1005]={0};
	int n=strlen(a);
	for(int i=1;i<=n;i++)
	{
		for(int l=1;l<=n-i+1;l++)
		{
			int r=i+l-1;
			dp[l][r]=dp[l+1][r]+1;
			for(int k=l+1;k<=r;k++)
			{
				if(a[l-1]==a[k-1])
				{
					dp[l][r]=min(dp[l+1][k]+dp[k+1][r],dp[l][r]);
				}
			}
		}
	}
	printf("%d\n",dp[1][n]);
}