Lintcode 593. Stone Game II

There is a stone game.At the beginning of the game the player picks n piles of stones in a circle.

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

At each step of the game,the player can merge two adjacent piles to a new pile.
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:
[1,1,4,4]
Output:18
Explanation:
1. Merge second and third piles => [2, 4, 4], score +2
2. Merge the first two piles => [6, 4]，score +6
3. Merge the last two piles => [10], score +10

Example 2:

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

Solution:
We make a copy of  the array A, and then the problem is the same as Stone game I. 
The main difference is for the final state, we should check all dp with length n

Code (Java):

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame2(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int n = A.length;
        int[] A2 = new int[n * 2];
        System.arraycopy(A, 0, A2, 0, n);
        System.arraycopy(A, 0, A2, n, n);
        int n2 = n * 2;
        
        int[][] dp = new int[n2 + 1][n2 + 1];
        int[] preSum = new int[n2 + 1];
        
        for (int i = 1; i <= n2; i++) {
            preSum[i] = preSum[i - 1] + A2[i - 1];
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n2 - 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]);
                }
            }
        }
        
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            ans = Math.min(ans, dp[i][i + n - 1]);
        }
        
        return ans;
        
    }
}