Coins in a line

This problem is from leetcode: http://articles.leetcode.com/2011/02/coins-in-line.html.

Number of coins lined up, two persons take turn to pick up coins from both ends, what is the maximum total sum of money first person can pick?

Many of the gaming type problems can be solved by dynamic programming. Say DP[i, j] presents the maximum value one person can gather if he/she is presented with coins from position i to j. The final answer will be DP[0][numofcoin-1].

When person presented with coins from i to j, he/she can either pick coin at i or j, after that, second person will pick the coins and we will assume second person is smart and will always make best move, that is, will minimize the first person can gain on the next step:

So we have the following formula for dynamic programming: 
DP(i,j) = Max(
         *     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
         *     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])


Here is the code:

public static int coinsInALine(int[] coins){
        //assume we have more than 4 coins, otherwise the problem becomes too easy
        /*
         * DP(i,j) = Max(
         *     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
         *     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])
         */
        int[][] table = new int[coins.length][coins.length];
        int[][] moves = new int[coins.length][coins.length];
        for(int i = 0; i<coins.length; i++){
            table[i][i] = coins[i];
            moves[i][i] = i;
        }
      
        for(int i=0; i<coins.length-1; i++){
            table[i][i+1] = Math.max(coins[i], coins[i+1]);
            moves[i][i+1] = coins[i] > coins[i+1]? i : i+1;
        }
      
        for(int step = 2; step<coins.length; step++){          
            for(int i=0; i+step<coins.length; i++){
                int a = coins[i+step] + Math.min(table[i][i+step-2], table[i+1][i+step-1]);              
                int b = coins[i] + Math.min(table[i+2][i+step], table[i+1][i+step-1]);
                table[i][i+step] = Math.max(a, b);  
                moves[i][i+step] = a > b? i+step : i;
            }
        }
      
        int i=0, j=coins.length-1;
        while(i<j){
            System.out.println("move: " + moves[i][j]);
            if(moves[i][j] == i)
                i++;
            else
                j--;
        }
        System.out.println("done");
        return table[0][coins.length-1];
    }