Problem

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. 
The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

Example
Given array A = [3,2,2], return true.

Given array A = [1,2,4], return true.

Given array A = [1,20,4], return false.

思路

• 画搜索图
  • 一开始把状态定义成,
    • dp[i]: 剩下i个硬币, 先手能获得的最大价值
  • 由于叶子节点的状态不一样却都代表dp[1], 所以如果要准确代表某个位置的值, 需要用区间来表示
  • state:
    • dp[i][j]: 表示剩下第i到第j个硬币, 先手获得的最大价值
  • function:
    • 
    • left = min(dp[i+2][j], dp[i+1][j-1])+coin[i] [i+1,j]
    • right = min(dp[i][j-2], dp[i+1][j-1])+coin[j] [i,j-1]
    • dp[i][j] = max(left, right).
  • Initialize:
    • dp[i][i] = num[i];
    • 另外, 由 i <= j - 2 可得, j = i + 1需要被初始化
    • dp[i][i + 1] = max{coin[i], coin[i + 1]}
  • answer:
    • dp[0][n] > sum / 2
  • 注意:
    • 和 Coins in a Line II 的区别, state 的定义,
      • 这里的是剩下第i个到第j个
      • II 的是剩下i个, 所以要注意所加的index

记忆化搜索

    public boolean firstWillWin(int[] values) {
        if (values == null) {
            return true;
        }

        int n = values.length;

        boolean[][] visited = new boolean[n][n];
        int[][] dp = new int[n][n];

        int sum = 0;
        for (int e: values) {
            sum += e;
        }

        return search(values, dp, visited, 0, n - 1) * 2 > sum;
    }

    private int search (int[] values, int[][] dp, boolean[][] visited, int i, int j) {
        if (visited[i][j]) {
            return dp[i][j];
        }

        visited[i][j] = true;

        if (i > j) {
            dp[i][j] = 0;
        }else if (i == j) {
            dp[i][j] = values[i];
        } else if (i + 1 == j) {
            dp[i][j] = Math.max(values[i], values[j]);
        } else {
            int left = Math.min(search(values, dp, visited, i + 2, j), search(values, dp, visited, i + 1, j - 1)) + values[i];
            int right = Math.min(search(values, dp, visited, i, j -2), search(values, dp, visited, i + 1, j - 1)) + values[j];
            dp[i][j] = Math.max(left, right);
        }

        return dp[i][j];
    }