[dynamic planning] p4170: coloring (interval DP)

 

 

initialization ：

Because of the demand minimum value , all dp Initialize to INF

When the interval length is 1 when ,dp by 1 

Enumerate small intervals first when enumerating

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int dp[51][51];
int main(){
	string s;
	cin>>s;
	int n=s.size();
	memset(dp,0x3f3f,sizeof(dp));
	for(int i=1;i<=n;i++){
		dp[i][i]=1;
	}

	for(int len=2;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			if(s[i-1]==s[j-1]){
				dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
			}
			else{
				for(int k=i;k<j;k++){
					dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
				}
			}
		}
	}
	cout<<dp[1][n]; 
	
}

Refer to the explanation of the question ：

Answer key P4170 【[CQOI2007] Coloring 】 - dzz The blog of - Luogu blog