lintcode 476. 石子归并

经典区间dp问题

链接

这道题里dp[i][j] 代表归并i 到j 所需要的最小成本，

对于k, 有j> k >= i

dp[i][j] = min(dp[i][k] + dp[k+1][j] + weights(i,j))， （因为每次合并两堆，倒数第二次肯定是剩下两堆）

这个即为状态方程，本题的dp写法可以作为模板式的区间dp做法

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame(int[] A) {
        // write your code here
        if(A == null || A.length == 0){
            return 0;
        }
        int n = A.length;
        int[][] dp = new int[n][n];
        //初始化，合并同一堆不需要重量成本
        for(int i = 0; i < n; i++){
            dp[i][i] = 0;
        }
        for(int l = 2; l <= n; l++){
            for(int i = 0; i + l - 1 < n; i++){
                int j = i + l - 1;
                dp[i][j] = Integer.MAX_VALUE;
                int wei = wei(A, i, j);
                for(int k = i; k < j; k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + wei);
                }
            }
        }
        return dp[0][n-1];
        
    }
    //别忘了每次合并还需要两堆重量
    int wei(int[]A, int s, int e){
        int wei = 0;
        for(int i = s; i <= e; i++){
            wei += A[i];
        }
        return wei;
    }
}