这个方程有两种形式，本文采用
if(s[i]=s[j]) dp[i][j]=d[i-1][j-1]
dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]) (i=<k<j)
其实与另一种方法比较：根据j的所有匹配情况取最小值
1.i到j无匹配，取为dp[i][j-1]+1
2.列举所有匹配情况 dp[i][k-1]+dp[k+1][j]
取上述所有情况最小值
两者都能获得正确的结果。
同时两者的初始化为 dp[i][j]==1 if(i==j)
规划方向为：
（1） （2） （3） （4）填写顺序
| 1 | （1） | （3） | （6） | （10） |
| 1 | （2） | （5） | （9） | |
| 1 | （4） | （8） | ||
| 1 | （7） | |||
| 1 |
// ConsoleApplication8.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<string>
#include<memory.h>
using namespace std;
#define min(x,y) (x < y ? x : y) bool isEqual(char c,char b)
{
if(c=='('&&b==')') return true;
if(c=='['&&b==']') return true;
return false; } int main()
{
int dp[][]; int len;
cin>>len;
while(len--)
{
string a;
cin>>a;
int len=a.length();
memset(dp,,sizeof(dp));//clear
dp[][]=;
for(int i=;i<len;i++)
{
dp[i][i]=; for(int j=i-;j>=;j--)
{
dp[j][i]=;
if(isEqual(a[j],a[i]))
{
dp[j][i]= min(dp[j][i],dp[j+][i-]);
}
for(int k=j;k<i;k++)
{
dp[j][i]=min(dp[j][k]+dp[k+][i],dp[j][i]); } } } cout<<dp[][len-]<<endl; } }
// ConsoleApplication8.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<string>
#include<memory.h>
using namespace std;
#define min(x,y) (x < y ? x : y) bool isEqual(char c,char b)
{
if(c=='('&&b==')') return true;
if(c=='['&&b==']') return true;
return false; } int main()
{
int dp[][]; int len;
cin>>len;
while(len--)
{
string a;
cin>>a;
int len=a.length();
memset(dp,,sizeof(dp));//clear
// cout<<dp[45][56]<<endl;
dp[][]=;
dp[][]=;
for(int i=;i<=len;i++)
{
dp[i][i]=; for(int j=i-;j>=;j--)
{
dp[j][i]=dp[j][i-]+; //没有匹配的情况
for(int k=j;k<i;k++)
{
if(isEqual(a[k-],a[i-]))
{
dp[j][i]= min(dp[j][i],dp[j][k-]+dp[k+][i-]);
} } } } cout<<dp[][len]<<endl; } }