一些典型DP题的代码

				#include 
				#include 
				#include 
				using namespace std;
				
				//最大符号匹配 动态规划
				/*
				输入：
				([][][)
				(])(
				((()))
				[][][]
				
				输出：
				6
				2
				6
				6
				*/
				#define NMAX 102
				int f[NMAX][NMAX];//f[i][j],从第i位到第j位子串的匹配情况
				char str[NMAX];//将shuru[]后移一位得道，str[0]不用，方便写转移方程
				char shuru[NMAX];
				
				void print(int num)
				{	//调试时打印f[][]
					int i,j;
					for(i=1;i					cout					for(i=1;i					{
						for(j=1;j							cout						cout					}
					cout					system("pause");
				}
				int cal(int num)
				{
					int i,j,max,k,m;
					memset(f,0,sizeof(f));
					for(i=1;i					for(i=1;i					{
						if((str[i]=='('&&str[i+1]==')')||(str[i]=='['&&str[i+1]==']'))
							f[i][i+1]=1;
					}
					for(k=3;k					{//要枚举的字符串长度
						for(i=1;i						{//要枚举的字符串的起始位置
							j=i+k-1;//结束位置
							max=f[i][j-1];
							if(str[j]==')'||str[j]==']') 
							{	//这种情况才可能增加匹配数
								for(m=i;m								{//枚举要与末括号匹配的括号位置
									if(m>i)
									{//如果m不是首位，max由三部分组成（1+str[m]之前+str[m]之后的匹配数）
										if((str[m]=='('&&str[j]==')')||(str[m]=='['&&str[j]==']'))
										{
											if(max												max=1+f[i][m-1]+f[m+1][j-1];
										}
										else if(max									}
									else
									{//如果m是首位，max由两部分组成（1+str[m]之后的匹配数）
										if((str[m]=='('&&str[j]==')')||(str[m]=='['&&str[j]==']'))
										{
											if(max												max=1+f[m+1][j-1];
										}
										else if(max									}
								}
							}
							f[i][j]=max;
						}
					}
				//	print(num);
					return f[1][num];
				}
				
				int main()
				{
					int i,num;
					scanf("%s",&shuru);
					while(strcmp(shuru,"end")!=0)
					{
						num=strlen(shuru);
						i=0;
						str[0]='s';
						do
						{
							str[i+1]=shuru[i];
							i++;
						}while(shuru[i-1]!='\0');
						cout						scanf("%s",&shuru);
					}
				    return 0;
				}