Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, PRedict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

Input: [1, 5, 2]Output: FalseExplanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]Output: TrueExplanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.Any scores in the given array are non-negative integers and will not exceed 10,000,000.If the scores of both players are equal, then player 1 is still the winner.
【問題分析】
 1、該問題是兩個人交替從一個數組兩端獲取一個數字，每次每個人只能獲取一個，最終獲取的數字之和最大的獲勝，問第一個人能否獲勝
 2、該問題的解法有兩種: 
        一種是建立二叉樹方法:
        A、建立兩顆二叉樹，第一顆的根節點是第一個數字，第二顆的根節點是第二個數字
        B、建樹過程每次從當前剩余元素中取最左端和最右端的元素，分別作為當前節點的左孩子和右孩子，依次遞歸建立二叉樹
        C、兩棵樹從根節點到葉節點的路徑總個數為2^(n-1)個，遍歷所有路徑，依次計算路徑中1、3、5...個節點之和，
        D、如果大于所有節點只和的一半，或者大于2、4、6...節點數字只和，則第一個取數字者可以獲勝，否則無法獲勝
        另一種是動態規劃算法:
        A、問題定義是：從數組下標0到n-1之間取數字的規則是交替進行，第一個人從數組首或尾取一個，第二個人從剩余數組元素首或尾取一個，
               依次交替直到取完所有數字
        B、定義dp[i][j] 表示數組下標i到j之間取數字為子問題，它等于能夠在i到j之間獲得的所有數字之和和的最大值
               目標是第一個人能否在0到n-1之間的所有數字中取得數字只和大于數組所有元素之和的1/2，即dp[0][n-1]
        C、dp[i][j]表示第一個人能夠從i到j之間獲取的所有數字之和的最大值，那么
               dp[i+1][j]表示第二個人能夠在i-1到j之間獲取的所有數字之和的最大值，
               dp[i][j-1]表示第二個人能夠在i到j-1之間獲取的所有數字之和的最大值
        D、sum[i+1][j] - dp[i+1][j]表示第一個人取第i個元素以后，能夠在i+1到j之間獲取子數組之和的最大值
               sum[i][j-1] - dp[i][j-1]標識第一個人取第j個元素以后，能夠在i到j-1之間獲取子數組之和的最大值
               由于dp[i][j]表示每個人都試圖獲取當前下標i到j之間字數組之和最大值，
               因此當剩余數組下標為i到j時，
               當第一個人取第i個元素之后，第二個人也在試圖獲取i+1到j之間的子數組之和最大dp[i+1][j]，此時第一個人能夠在i到j之間獲取的最終子數組之和為
               nums[i] + sum[i+1][j] - dp[i+1][j]           // 后半部分表示第二個人獲取最大子數組以后，剩余的字數組之和，也是第一個人只能選擇的子數組
               遞推公式如下：
               當第一個人獲取第i個元素時，dp[i][j] = nums[i] + sum[i+1][j] - dp[i+1][j] = dp_left
               當第一個人獲取第j個元素時，dp[i][j] = nums[j] + sum[i][j-1] - dp[i][j-1]  = dp_right
               第一個人想獲勝，因此dp[i][j] = max(dp_left, dp_right)
               當i == j時，只有一種選擇，dp[i][j] = nums[i]
               當i == j-1 時，只有兩種選擇，dp[i][j] = max(nums[i], nums[j])
               i到j之間的數組之和可以表示為sum[i][j] = sum[0][j] - sum[0][i-1] = sum(j) - sum(i-1)
               
【AC代碼】
class Solution3 {    public:        bool PredictTheWinner(std::vector<int>& nums) {            std::vector<std::vector<int> > dp(nums.size(), std::vector<int>(nums.size()));            std::vector<int> prefix_sum(nums.size()+1);            prefix_sum[0] = 0;            for (int i = 0; i < nums.size(); ++i) {                prefix_sum[i+1] = prefix_sum[i] + nums[i]; //下標從i+1開始            }            for (int len = 1; len <= nums.size(); ++len) {                for(int lhs = 0; lhs + len - 1 < nums.size(); ++lhs) {                    int rhs = lhs + len - 1;                    if (lhs == rhs) {                        dp[lhs][rhs] = nums[lhs];                    }                    else if(lhs == rhs - 1) {                        dp[lhs][rhs] = std::max(nums[lhs], nums[rhs]);                    }                    else {                        int dp_left = nums[lhs] + prefix_sum[rhs+1] - prefix_sum[lhs+1] - dp[lhs+1][rhs];                        int dp_right = nums[rhs] + prefix_sum[rhs] - prefix_sum[lhs] - dp[lhs][rhs-1];                        dp[lhs][rhs] = std::max(dp_left, dp_right);                    }                }            }            return 2 * dp[0][nums.size()-1] >= prefix_sum.back();            //return dp[0][nums.size()-1] >= prefix_sum.back() / 2 + prefix_sum.back() % 2;        }};參考資料:
https://discuss.leetcode.com/topic/76327/c-dp-solution-with-explanation
https://discuss.leetcode.com/topic/76472/clean-3ms-c-dp-solution-with-detailed-explanation