石子合并

题目

有一个石子归并的游戏。最开始的时候，有n堆石子排成一列，目标是要将所有的石子合并成一堆。合并规则如下：

每一次可以合并相邻位置的两堆石子
每次合并的代价为所合并的两堆石子的重量之和
求出最小的合并代价。

样例

样例 1:

输入: [3, 4, 3]
输出: 17
样例 2:

输入: [4, 1, 1, 4]
输出: 18
解释:

合并第二堆和第三堆 => [4, 2, 4], score = 2
合并前两堆 => [6, 4]，score = 8
合并剩余的两堆 => [10], score = 18
解题思路
用DP[i][j]来表示把A[i…j]搬到一起需要的score。DP[left][right]可以表示成DP[left][j] + DP[j+1][right] + sum(i,j) 元素i到j求和，可以前缀和求得；即首先形成这两团需要的score，和把这两团加在一起的score（前缀和）。

len要大于等于2才有意义，因为要长度至少为2才能累加。枚举的区间长度，左边是i，右边是i + len - 1。

源码

class Solution {
public:
    /**
     * @param A: An integer array
     * @return: An integer
     */
    int stoneGame(vector<int> &A) {
        // write your code here
        int n = A.size();
        if(n==0)return 0;
        if(n==1)return 0;
        int *sum = (int *)malloc(sizeof(int)*n+1);
        
        sum[0]=0;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+A[i-1];
        
        // int dp[][]=new int[n][n];
        
        int **dp;
        dp=(int **)malloc(sizeof(int *)*n);
        for(int i=0;i<n;i++){
            dp[i]=(int *)malloc(sizeof(int)*n);
        }
        
        
        for(int i=0;i<n-1;i++){
            dp[i][i]=0;
            dp[i][i+1]=A[i]+A[i+1];
        }
        dp[n-1][n-1]=0;
        
        for(int len = 3;len<=n;len++){
            for(int i=0;i<=n-len;i++){
                int j=i+len-1;
                dp[i][j]=999999;
                for(int k=i;k<j;k++){
                    dp[i][j]=(dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]) < dp[i][j]?(dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]):dp[i][j];
                }
            }
        }
        
        return dp[0][n-1];
    }
};