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、該問題是兩個人交替從一個數(shù)組兩端獲取一個數(shù)字，每次每個人只能獲取一個，最終獲取的數(shù)字之和最大的獲勝，問第一個人能否獲勝
 2、該問題的解法有兩種: 
        一種是建立二叉樹方法:
        A、建立兩顆二叉樹，第一顆的根節(jié)點是第一個數(shù)字，第二顆的根節(jié)點是第二個數(shù)字
        B、建樹過程每次從當前剩余元素中取最左端和最右端的元素，分別作為當前節(jié)點的左孩子和右孩子，依次遞歸建立二叉樹
        C、兩棵樹從根節(jié)點到葉節(jié)點的路徑總個數(shù)為2^(n-1)個，遍歷所有路徑，依次計算路徑中1、3、5...個節(jié)點之和，
        D、如果大于所有節(jié)點只和的一半，或者大于2、4、6...節(jié)點數(shù)字只和，則第一個取數(shù)字者可以獲勝，否則無法獲勝
        另一種是動態(tài)規(guī)劃算法:
        A、問題定義是：從數(shù)組下標0到n-1之間取數(shù)字的規(guī)則是交替進行，第一個人從數(shù)組首或尾取一個，第二個人從剩余數(shù)組元素首或尾取一個，
               依次交替直到取完所有數(shù)字
        B、定義dp[i][j] 表示數(shù)組下標i到j之間取數(shù)字為子問題，它等于能夠在i到j之間獲得的所有數(shù)字之和和的最大值
               目標是第一個人能否在0到n-1之間的所有數(shù)字中取得數(shù)字只和大于數(shù)組所有元素之和的1/2，即dp[0][n-1]
        C、dp[i][j]表示第一個人能夠從i到j之間獲取的所有數(shù)字之和的最大值，那么
               dp[i+1][j]表示第二個人能夠在i-1到j之間獲取的所有數(shù)字之和的最大值，
               dp[i][j-1]表示第二個人能夠在i到j-1之間獲取的所有數(shù)字之和的最大值
        D、sum[i+1][j] - dp[i+1][j]表示第一個人取第i個元素以后，能夠在i+1到j之間獲取子數(shù)組之和的最大值
               sum[i][j-1] - dp[i][j-1]標識第一個人取第j個元素以后，能夠在i到j-1之間獲取子數(shù)組之和的最大值
               由于dp[i][j]表示每個人都試圖獲取當前下標i到j之間字數(shù)組之和最大值，
               因此當剩余數(shù)組下標為i到j時，
               當?shù)谝粋€人取第i個元素之后，第二個人也在試圖獲取i+1到j之間的子數(shù)組之和最大dp[i+1][j]，此時第一個人能夠在i到j之間獲取的最終子數(shù)組之和為
               nums[i] + sum[i+1][j] - dp[i+1][j]           // 后半部分表示第二個人獲取最大子數(shù)組以后，剩余的字數(shù)組之和，也是第一個人只能選擇的子數(shù)組
               遞推公式如下：
               當?shù)谝粋€人獲取第i個元素時，dp[i][j] = nums[i] + sum[i+1][j] - dp[i+1][j] = dp_left
               當?shù)谝粋€人獲取第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之間的數(shù)組之和可以表示為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