Stone Game -- Lintcode -- dp

Question:

http://www.lintcode.com/en/problem/stone-game/

There is a stone game.At the beginning of the game the player picksn piles of stones in a line.

The goal is to merge the stones in one pile observing the following rules:

1. At each step of the game,the player can merge two adjacent piles to a new pile.
2. The score is the number of stones in the new pile.

You are to determine the minimum of the total score.

Have you met this question in a real interview? 

Yes

Example

For [4, 1, 1, 4], in the best solution, the total score is 18:

1. Merge second and third piles => [4, 2, 4], score +2
2. Merge the first two piles => [6, 4]，score +6
3. Merge the last two piles => [10], score +10

Other two examples:
[1, 1, 1, 1] return 8
[4, 4, 5, 9] return 43

Solution:

dp mothod:

dp(i,j) = min{dp(i,k) + dp(k+1,j) + sum(i,j)},  when i<j

dp(i,j) = 0, when i=j

Space: sum[m][m], dp[m][m], O(2*m*m) = O(m*m); Time:O(m*m)

public class Solution {

    /**

     * @param A an integer array

     * @return an integer

     */

    public int stoneGame(int[] A) {

        // Write your code here

        int m=A.length;

        if(m==0)return 0;

        if(m==1)return 0;

        int[][] sum = new int[m][m];

        int[][] dp = new int[m][m];

        

        for(int i=0;i<m;++i){

            sum[i][i]=A[i];

            for(int j=i+1;j<m;++j){

                sum[i][j]=sum[i][j-1]+A[j];

            }

        }

        

        for(int j=1;j<m;++j){

            //dp edge case

            dp[j][j]=0;

            

            for(int i=j-1;i>=0;--i){

                

                int min = Integer.MAX_VALUE;

                //dp common case func

                for(int k=i;k<=j-1;++k){

                    int tmp = dp[i][k] + dp[k+1][j];

                    if(tmp < min){

                        min = tmp;

                    }

                }

                dp[i][j] = min + sum[i][j];

            }

        }

        return dp[0][m-1];

    }

}