求dp比较水。。但是打印路径很蛋疼。。搞了好久还学习了别人的递归写法
题目：
背景
给定一个正整数序列a(1)，a(2)，...，a(n),(1<=n<=20)
不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。
例如:
给出序列是4，1，2，3。
第一种添括号方法:
((4+1)+(2+3))=((5)+(5))=(10)
有三个中间和是5，5，10，它们之和为:5+5+10=20
第二种添括号方法
(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)
中间和是3，6，10，它们之和为19。
描述
现在要添上n-1对括号，加法运算依括号顺序进行，得到n-1个中间和，求出使中间和之和最小的添括号方法。
格式
输入格式
共两行。
第一行，为整数n。(1<=n<=20)
第二行，为a(1),a(2),...,a(n)这n个正整数，每个数字不超过100。
输出格式
输出3行。
第一行，为添加括号的方法。
第二行，为最终的中间和之和。
第三行，为n-1个中间和，按照从左到右，从里到外的顺序输出。
限制
各个测试点1s
来源
MaoLaoda
代码：
1 #include <iostream> 2 using namespace std; 3 #define INF 999999 4 int n; 5 int num[30]; 6 int sum[30]; 7 int dp[30][30]; 8 int G[30][30]; 9 10 int dfs( int L ,int R) 11 { 12 int &d = dp[L][R]; 13 if( d !=INF) return d; 14 15 if(L == R) return d=0; 16 if(L == R-1 ) 17 { 18 G[L][R] = L; 19 return d=num[L]+num[R]; 20 } 21 for(int i=L;i<R;i++) 22 { 23 int t = dfs(L, i)+dfs( i+1, R); 24 if ( d>= t) 25 { 26 d = t; 27 G[L][R] = i; 28 } 29 } 30 return d= d+ sum[R]-sum[L-1]; 31 } 32 void print(int L, int R) 33 { 34 if( L == R) 35 { 36 cout<<num[L]; 37 return; 38 } 39 cout<<"("; 40 print(L,G[L][R]); 41 cout<<"+"; 42 print(G[L][R]+1,R); 43 cout<<")"; 44 } 45 46 void init() 47 { 48 for(int i=0;i<=n;i++) 49 { 50 for(int j=0;j<=n;j++) 51 { 52 dp[i][j] = INF; 53 } 54 } 55 } 56 void pdfs(int L,int R) 57 { 58 if( L == R) 59 return ; 60 pdfs( L ,G[L][R]); 61 pdfs( G[L][R] +1, R); 62 if( L == 1 && R==n) cout<<sum[R]-sum[L-1]<<endl; 63 else 64 cout<<sum[R]-sum[L-1]<<" "; 65 } 66 int main() 67 { 68 69 cin>>n; 70 init(); 71 for(int i=1;i<=n;i++) 72 { 73 cin>>num[i]; 74 sum[i]= sum[i-1]+num[i]; 75 } 76 77 78 dfs(1,n); 79 80 print(1,n); 81 cout<<endl; 82 cout<<dp[1][n]<<endl; 83 pdfs(1,n); 84 return 0; 85 }