点击打开链接
刚学区间dp，所以先去上网搜了别人的代码，区间dp那点明白了，就是不断更新一个区间内需要填加括号的数目，直到值是最小值。然后是那个打印路径，那个地方一直没看懂，不明白为什么那样保存，然后自己手动模拟了一遍，又照着网上的代码敲了一遍才逐渐明白，其实就是保存一个区间是怎么分割的，把一个区间分成若干个子区间，怎样合并使值达到最小，区间值达到最小之后两个相邻的子区间断开的地方就是要保存的值，就是保存路径，接着就是打印路径，这个就不多说了，使用递归。以下是自己的代码，其实跟网上的差不多，关键是要完全理解这个知识。
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#define MAXN 0x3f3f3f3f
using namespace std;
int dp[105][105]; //记录i到j需要添加多少括号
int pos[105][105]; //记录从i到j从哪里断开，保存路径
char str[105];
void print(int i,int j)
{