1.实验目的

(1)掌握动态规划法的处理思路与算法框架。

(2)掌握应用动态规划法解决具体问题的方法。

(3)掌握动态规划法的广泛应用。

2.实验内容

(1)问题描述

括号序列有()、{}和[]组成。

（1）设计一个算法来判断括号序列不合法，如“(([{}]))”是合法的，而“(}{)”、“(}(}”和“({)}”都是不合法的。

（2）如果一个括号序列不合法，设计一个算法，求解使该序列成为合法的括号序列至少需要添加的括号数目。例如，“(}(}”最少需要添加4个括号成为合法括号序列，即变为“(){}(){}”。

(2)输入

输入只有一行。

第一行包含一个字符串，它的长度为。这个字符串仅由小括号、中括号或大括号，即’(’,’)’,’[’,’]’,’{’或’}’组成。字符的下标从0开始。

(3)输出

输出分为两行。

第一行输出True或False。True表示括号序列是合法序列，False表示括号序列不是合法序列。

第二行输出使该序列成为合法的括号序列至少需要添加的括号数目。

3.问题实例分析

 实例：输入参数str=[({}}。

 首先解决问题1。该括号序列是否为一个合法序列？

 可以利用栈这一数据结构进行解决。遍历当前序列，每碰到一个左括号就入栈，放入栈顶。碰到一个右括号时，判断当前右括号与左括号是否匹配。若匹配，则将左括号出栈。若不匹配，则无需遍历后续括号序列，结束遍历，能直接能说明当前括号序列为不合法序列。在遍历完序列后，若栈不为空，则说明还有左括号没被右括号匹配上。同样的，这也是个不合法的括号序列。

 言而简之，当且仅当括号序列能被遍历完且遍历完时栈为空，括号序列才能为合法序列。

 在本实例中，初始时栈为空，首先将第0个字符左中括号“[”入栈，再将第1个字符左小括号“(”入栈，将第2个字符左大括号“{”入栈。第3个字符为“}”，与栈顶的左大括号“{”匹配了，出栈。第4个字符为“}”，与栈顶“(”不匹配，则说明当前序列不是合法序列。

 解决问题2。求解使该序列成为合法序列所需要添加的最少的括号数目。我们也可以自底向上地解决这个问题。

 先将这个问题分解为若干个规模较小且相等的子问题：只有1个括号时使得括号序列合法化所需的括号数目，只有2个括号时使得括号序列合法化所需的括号数目。3个或多个括号合法化时所需的括号数量可以分解为上述的子问题。

五个字符

4.算法描述及说明

5.算法正确性分析

 算法会正确地结束：在运行完成三重循环后，算法会停止。

7.运行结果展示及其说明

测试样例使用了三组。对于每一组测试样例，都正确地输出了该括号序列是否合法，以及使得括号序列变为合法序列所需的括号数目。

8.心得体会

9.程序源代码

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
string str;
int dp[1005][1005];
bool check(int i, int j) {
  if ((str[i] == '(') && (str[j] == ')') || (str[i] == '[') && (str[j] == ']') || (str[i] == '{') && (str[j] == '}'))
    return true;
  else return false;
}
int main() {
  cin >> str;
  int maxlen = str.size();
  for (int len = 1; len <= maxlen; len++) {
    for (int l = 0; l + len - 1 < maxlen; l++) {
      int r = l + len - 1;
      if (len == 1)
        dp[l][r] = 1;
      else {
        dp[l][r] = 0x3f3f3f3f;
        if (check(l, r)) {
          dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
        }
        for (int k = l; k <= r; k++)
          dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
      }
    }
  }
  if (dp[0][maxlen - 1] == 0)
    cout << "True\n";
  else
    cout << "False\n";
  cout << dp[0][maxlen - 1];
  return 0;
}