1.石子归并问题
dp[i][j]表示区间i到j合并所需的最小花费。
先求出小区间的最小花费，再转移到大的区间。
转移方程：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
初始状态：dp[i][i]=0
模板：
for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i] for(int l=2;l<=n;l++){ for(int i=1;i+l-1<=n;i++){ int j=i+l-1; dp[i][j]=INF; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } }