Lintcode 476. Stone Game

There is a stone game.At the beginning of the game the player picks n 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.

Example

Example 1:

Input: [3, 4, 3]
Output: 17

Example 2:

Input: [4, 1, 1, 4]
Output: 18
Explanation:
  1. Merge second and third piles => [4, 2, 4], score = 2
  2. Merge the first two piles => [6, 4]，score = 8
  3. Merge the last two piles => [10], score = 18

Solution:
This is a interval dp problem. Define dp[n+ 1][n + 1] where dp[i][j] means the minimum score for merging ith and jth stones we can get. 

So dp[i][j]  = max(dp[i][k] + dp[k + 1][j] + presum[j] - presum[i  -1]; where k >= i && k < j
Note the computation order should be in the length.

Code (Java):

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int n = A.length;
        int[][] dp = new int[n + 1][n + 1];
        
        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + A[i - 1];
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1 ;i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + preSum[j] - preSum[i - 1]);
                }
            }
        }
        
        return dp[1][n];
    }
}

Update on 2/19/2021:

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;
        }
        
        if (A.length == 1) {
            return 0;
        }
        
        int n = A.length;
        
        int[][] dp = new int[n][n];
        
        
        int[] presum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            presum[i] = presum[i - 1] + A[i - 1];
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + presum[j + 1] - presum[i] );
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

Use Memo search:

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;
        }
        
        if (A.length == 1) {
            return 0;
        }
        
        int n = A.length;
        
        int[][] dp = new int[n][n];
        
        int[] presum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            presum[i] = presum[i - 1] + A[i - 1];
        }
        
        return stoneGameHelper(A, 0, n - 1, dp, presum);
    }
    
    private int stoneGameHelper(int[] A, int start, int end, int[][] dp, int[] presum) {
        if (start == end) {
            return 0;
        }
        
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        
        int score = Integer.MAX_VALUE;
        for (int k = start; k < end; k++) {
            int left = stoneGameHelper(A, start, k, dp, presum);
            int right = stoneGameHelper(A, k + 1, end, dp, presum);
            
            score = Math.min(score, left + right + presum[end + 1] - presum[start]);
        }
        
        dp[start][end] = score;
        
        return score;
    }
}