DP试水题,参考刘汝佳《算法艺术与信息学竞赛》,书中精髓也点出来了,寻找合适的状态(满足最优子结构,无后效性),同时要编写合适的状态转移方程,这时候写出来的朴素的算法一般都是指数时间复杂度的,这时候再利用DP的两个方法优化
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn= 1e2+5;
char ar[maxn];
int dp[maxn][maxn], p[maxn][maxn];
void Init(int n)
{
memset(dp, 0x3f, sizeof(dp));
memset(p, -1, sizeof(p));
for (int i= 1; i<= n; ++i){
dp[i][i-1]= 0;
dp[i][i]= 1;
}
}
void Solve(int l, int r)
{
if (l> r){
return;
}
if (l== r){
if ('('== ar[l] || ')'== ar[l]){
cout<<"()";
}
else{
cout<<"[]";
}
return;
}
if (-1== p[l][r]){
cout<<ar[l];
Solve(l+1, r-1);
cout<<ar[r];
}
else{
Solve(l, p[l][r]);
Solve(p[l][r]+1, r);
}
}
int main(int argc, char const *argv[])
{
int len;
scanf("%s", ar+1);
len= strlen(ar+1);
Init(len);
for (int d= 1; d<= len-1 ; ++d){
int ub= len-d;
for (int i= 1; i<= ub; ++i){
int j= i+d, t;
if ( ('(' == ar[i] && ')' == ar[j])
|| ('[' == ar[i] && ']' == ar[j]) ){
dp[i][j]= dp[i+1][j-1];
}
for (int k= i; k< j; ++k){
t= dp[i][k]+dp[k+1][j];
if (t< dp[i][j]){
dp[i][j]= t;
p[i][j]= k;
}
}
}
}
Solve(1, len);
putchar('\n');
return 0;
}