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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

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:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

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:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

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;     } }