石子合并

 假设只有2堆石子，显然只有1种合并方案  如果有3堆石子，则有2种合并方案，((1,2),3)和(1,(2,3))  如果有k堆石子呢？ 

                           

不管怎么合并，总之最后总会归结为2堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解。

令m[i,j]表示归并第i个数到第j数的最小代价,w[i,j]表示第i个数到第j个数的和，这个可以事先计算出来。有如下的状态转移方程: 

                 

预处理w[i][j]：  

先算出前缀和s[i]，然后w[i][j] = s[j] – s[i-1]  

因此，w[i][j]可以不事先存放，在DP时直接O

(1)计算   s[0] = 0;   for(int i = 1; i<=n; i++) s[i] = s[i-1]+a[i]; 

拓展成环：  

对于环状序列，通用的处理方法是把这条链延长2倍，扩展成2n-1堆，其中第1堆与n+1堆完全相同，第i堆与n+i堆完全相同，这样我们只要对这2n堆动态规划后，枚举f(1,n),f(2,n+1),…,f(n,2n-1)取最优值即可即可。 

                         

  

#include<bits/stdc++.h>
using namespace std;
int dp[305][305],len,a[305],n,sum[305];
int main()
{
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        dp[i][i]=0;
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            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]);
            }
        }
    }
    cout<<dp[1][n];
}