题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
int f[N][N];
int n;
int a[N];
int dfs(int l,int r)
{
if(l>=r) return 0;
if(f[l][r]!=-1) return f[l][r];
int res=0x3f3f3f3f;
f[l][r]=0;
if(a[l]==a[r]) res=min(res,dfs(l+1,r-1)+1);
if(a[l]==a[l+1]) res=min(res,dfs(l+1,r));
if(a[r]==a[r-1]) res=min(res,dfs(l,r-1));
res=min({res,dfs(l,r-1)+1,dfs(l+1,r)+1});
return f[l][r]=res;
}
int main()
{
cin>>n;
int m=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
memset(f,-1,sizeof(f));
dfs(1,n);
if(f[1][n]==-1) f[1][n]=0;
cout<<f[1][n];
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
打卡