经典区间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;
}
}
