動态規劃——Zuma（區間dp）

題目連結

題目大意

Genos 最近在他的手機上下載下傳了祖瑪遊戲。在祖瑪遊戲裡，存在 n 個一行的寶石，第i個寶石的顔色是 Ci 。這個遊戲的目标是盡快的消滅一行中所有的寶石。 在一秒鐘，Genos 能很快的挑選出這些有顔色的寶石中的一個回文的，連續的子串，并将這個子串移除。每當一個子串被删除後，剩餘的寶石将連接配接在一起，形成一個新的行列。你的任務是：求出把整個寶石串都移除的最短時間。 讓我們給你一個提示：如果一個串正着讀或倒着讀都一樣，那麼這個串（或子串）叫回文串。在我們這道題中，“回文”指這個寶石串中的第一個珠子的顔色等于最後一個珠子的顔色，第二個珠子的顔色等于倒數第二個珠子的顔色，等等。 輸入輸出格式 輸入格式：

第一行包含一個整數 n(1 <= n <= 500) ——寶石串的長度。 第二行包含 n 個被空格分開的整數，第 i(1 <= i <= n) 個表示這行中第 i 個珠子的顔色。 輸出格式：

輸出一個整數，把這行珠子移除的最短時間。

輸入輸出樣例

輸入樣例 1

3

1 2 1

輸出樣例 1

1

輸入樣例 2

3

1 2 3

輸出樣例 2

3

輸入樣例 3

7

1 4 4 2 3 2 1

輸出樣例 3

2

說明：

在第一個例子中，Genos 可以在一秒鐘就把這行珠子全部移走。 在第二個例子中，Genos 一次隻能移走一個珠子，是以移走三個珠子花費他三秒。 在第三個例子中，為了達到 2 秒的最快時間，先移除回文串 4 4,再移除回文串 1 2 3 2 1。

分析

狀态轉移方程為：

dp[ i ][ i ] = 1

dp[ i ][ i + 1 ] = 1 (c[ i ] = c[ i + 1 ])

dp[ i ][ j ] = min(dp[ i ][ j ],dp[ i + 1 ][ j - 1 ]) (c[ i ] = c[ j ])

dp[ i ][ j ] = min(dp[ i ][ j ],dp[ i ][ t ]+dp[ t + 1 ][ j ]) (c[ i ] != c[ j ] && i ≤ t < j )

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,c[505],dp[505][505];

int main()
{
	cin>>n;
	memset(dp,inf,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=1;
		if(c[i]==c[i+1]){
			dp[i][i+1]=1;
		}
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n;i++){
			int j=i+len-1;
			if(j>n){
				break;
			}
			if(c[i]==c[j]){
				dp[i][j]=min(dp[i][j],dp[i+1][j-1]);	
			}
			for(int t=i;t<j;t++){
				dp[i][j]=min(dp[i][j],dp[i][t]+dp[t+1][j]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}