class Solution {
public:
    /*
     * @param : a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> values) {
        // write your code here
        int size = values.size();
        if (size == 0) {
            return false;
        }

        //vector<vector<int>> dp(size + 1, vector<int>(size + 1, 0));
        //vector<vector<bool>> visited(size + 1, vector<bool>(size + 1, false));

        vector<vector<int>> dp(size, vector<int>(size, 0));
        vector<vector<bool>> visited(size, vector<bool>(size, false));

        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += values[i];
        }
        return sum < 2 * memorySearch(0, size - 1, values, dp, visited);
    }
    // 递归的定义：在values数组里，从start index 到 end index 的区间中，先手所能获取硬币的最大总价值是多少；
    int memorySearch(int start, int end, vector<int>& values, vector<vector<int>>& dp, vector<vector<bool>>& visited) {
        if (visited[start][end]) {
            return dp[start][end];
        }

        if (start == end) {
            dp[start][end] = values[start];
        } else if (start + 1 == end) {
            dp[start][end] = max(values[start], values[end]);
        } else if (start > end) {
            dp[start][end] = 0;
        } else {
            int left_side = values[start] + min(memorySearch(start + 2, end, values, dp, visited), memorySearch(start + 1, end - 1, values, dp, visited));
            int right_side = values[end] + min(memorySearch(start + 1, end - 1, values, dp, visited), memorySearch(start, end - 2, values, dp, visited));
            dp[start][end] = max(left_side, right_side);
        }
        visited[start][end] = true;
        return dp[start][end];
    }
};