双倍经验qwq
Description
初始时数组为空，每次可以选择一个区间\(l-r\)将其赋为同一个值，赋的值可以覆盖，给定数组的目标形式，求至少经过多少次操作使得空数组变成目标形式。
Solution
我们发现每次选择一个区间，大区间包含小区间，小区间可以推到大区间。因此考虑区间dp。
如何转移呢？
我们发现若数组为\(a\),左区间为\(l\),右区间为\(r\),若\(a_l = a_r\)，则给区间\(l-r\)染色是不是就等于给区间\(l-(r-1)\)染色？因此我们得出部分状态转移方程：\(f_{l,r}=f_{l,r-1}(a_l=a_r)\)
需要注意初始化将\(f_{i,i}=1\)。因为区间若left=right只有一个数，是需要一次染色的。
剩下的就是区间之间的转移，枚举分组位置\(k\)套分组dp板子即可。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#define N 1001
#define INF 0x3f3f3f3f
using namespace std;
string str;
char ch[N];
int len;
int f[N][N];
int main()
{
int p;
scanf("%d",&p);
scanf("%s",ch+1);
len = strlen(ch+1);
for(int i = 1;i <= len;i++) f[i][i] = 1;
for(int i = 2;i <= len;i ++)
{
for(int l = 1;l <= len&&l+i-1 <= len;l++)
{
int r = l+i-1;
f[l][r] = INF;
if(ch[l] == ch[r]) f[l][r] = f[l][r-1];
for(int k=l;k<=r;k++) f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]);
}
}
cout<<"qwq"<<endl;
cout<<f[1][len]<<endl;
return 0;
}