2 Player and N Coin

 1 class Solution {
 2 
 3     public void printChoices(int[] A, int[][] C) {
 4         System.out.println("硬币列表如下:");
 5         for(int i=0,l=A.length; i<l; i++) {
 6             System.out.print(A[i] + "	");
 7         }
 8         System.out.println("");
 9         final int N = C.length;
10         String[] names = {"本人", "对手"};
11         int L = 0, R = N-1, WHO = 0;
12         while(L<=R) {
13             int c = C[L][R];
14             System.out.println(names[WHO] + "选择第 " + c + " 个元素" + A[c]);
15             WHO = (WHO+1)%2;
16             if(L==c) {
17                 L = L+1;
18             }
19             if(R==c) {
20                 R = R-1;
21             }
22             if(L == R) {
23                 break;
24             }
25         }
26     }
27 
28     public int maxMoney(int[] A) {
29         final int N = A.length;
30         int[][] C = new int[N][N];
31         int[][] M = new int[N][N]; // 每个子问题最优解（赚的最多钱）
32 
33         // 设M(i,j) 为从第i到第j个硬币中能获得的最大收入
34         // j-i>=2 时
35         // M(i,j) = max(
36         //      A[i] + min(M(i+2,j), M(i+1,j-1)),
37         //      A[j] + min(M(i+1,j-1), M(i,j-2)),
38         // );
39 
40         // 初始化坐标 [i,i] 和 [i,i+1] 处的决策和最大收入
41         for(int i=0; i<N; i++) {
42             M[i][i] = A[i];
43             C[i][i] = i;
44             if(i<N - 1) {
45                 M[i][i+1] = Integer.max(A[i], A[i+1]);
46                 C[i][i+1] = (A[i] < A[i+1] ? i+1 : i);
47             }
48         }
49 
50         // 计算所有 [i,i+2] [i,i+3]... 处的决策和最大收入
51         for(int i=N-2; i>=0; i--) {
52             for(int j=i+2; j<N; j++) {
53                 int I = A[i] + Integer.min(M[i+2][j], M[i+1][j-1]);
54                 int J = A[j] + Integer.min(M[i+1][j-1], M[i][j-2]);
55                 M[i][j] = Integer.max(I, J);
56                 C[i][j] = I>J ? i : j;
57             }
58         }
59 
60         printChoices(A, C);
61         return M[0][N-1];
62     }
63 
64     public static void main(String[] args) {
65         Solution s = new Solution();
66         int[] a = {1,20,10,2};
67         int r = s.maxMoney(a);
68         System.out.println(r);
69     }
70 }