We have a list of piles of stones, each pile of stones has a certain weight, represented by an array of integers. In each move, we can merge two adjacent piles into one larger pile, the cost is the sum of the weights of the two piles. We merge the piles of stones until we have only one pile left. Determine the minimum total cost.

Assumptions

• stones is not null and is length of at least 1

Examples

{4, 3, 3, 4}, the minimum cost is 28

• merge first 4 and first 3, cost 7

• merge second 3 and second 4, cost 7

• merge two 7s, cost 14

• total cost = 7 + 7 + 14 = 28

Solution 1: 中心开花

先用sum[i][j]记录i到j的stones weight的和

M[i][j] : min cost of merging between index i and j

base case: M[i][i] = 0

induction rule : 从size = 1出发，逐渐增大size，遍历在[i, i + size) 的j,

M[i][i + size] = min(M[i][i + size], M[i][j] + M[j + 1][i + size] + sum[i][i + size])

  public int minCost(int[] stones) {
    int[][] cost = new int[stones.length][stones.length];
    int[][] sum = new int[stones.length][stones.length];
    //其实这个循环可归入求cost[i][j]的循环
    for (int i = 0; i < sum.length; i++) {
      sum[i][i] = stones[i];
      for (int j = i + 1; j < sum.length; j++) {
        sum[i][j] = sum[i][j - 1] + stones[j];
      }
    }
    for (int size = 1; size < stones.length; size++) {
      for (int i = 0; i < stones.length - size; i++) {
        cost[i][i + size] = Integer.MAX_VALUE;
        for (int j = i; j < i + size; j++) {
          int temp = cost[i][j] + cost[j + 1][i + size] + sum[i][i + size];
          cost[i][i + size] = Math.min(cost[i][i + size], temp);
        }
      }
    }
    return cost[0][cost.length - 1];
  }

Solution 2: 记忆化搜索，

dp[m][n] = Math.min(dp[m][n], memorySearch(A, dp, m, k, sum) + memorySearch(A, dp, k + 1, n, sum) + sum[m][n]) k∈[m, n)

    public int stoneGame(int[] A) {
        if(A == null || A.length == 0){
            return 0;
        }
        int[][] dp = new int[A.length][A.length];
        int[][] sum = new int[A.length][A.length];
        for(int i = 0; i < A.length; i++){
            for(int j = i; j < A.length; j++){
                if(i == j){
                    sum[i][j] = A[i];
                    continue;
                }
                sum[i][j] = sum[i][j - 1] + A[j];
            }
        }
        return memorySearch(A, dp, 0, A.length - 1, sum);
    }

     private int memorySearch(int[] A, int[][] dp, int m, int n, int[][] sum){
        if(m >= A.length || n < 0 || m > n){
            return 0;
        }
        if(dp[m][n] != 0){
            return dp[m][n];
        }
        if(m == n){
            dp[m][m] = 0;
        } else{
            dp[m][n] = Integer.MAX_VALUE;
            for(int k = m; k < n; k++){
               dp[m][n] = Math.min(dp[m][n], memorySearch(A, dp, m, k, sum) + memorySearch(A, dp, k + 1, n, sum) + 
                          sum[m][n]);

           }
        }
        return dp[m][n];
    }