leetcode15，leetcode877.StoneGame

題目：一個數組，倆人從里面取數，要么從最左邊取，要么從最右邊取，直至把所有數取完，若第一個人取得所有數之和比第二個人取得數之和大，則為true

輸入：一個整型數組

輸出：true or false

leetcode15。別人思路：
　　使用動態規劃的思想：設dp[i][j]表示從piles[i]到piles[j]你可以比對手多得的最多的分數。這樣我們的最終目標是dp[0][n-1]。
　　現在我們需要確定轉移方程和初始條件。在piles[i]~piles[j]中，你可以選擇piles[i]或者piles[j]：
　　如果你選擇了piles[i]，那么你的對手就會從piles[i+1]~piles[j]中得到最多的分數，分數差值為piles[i]-dp[i+1][j].(題目要求都發揮最佳水平，所以對于對手而言dp的含義一樣。,他會從剩下的piles中選擇最多的分數，所以兩者做減法。）
　　如果你選擇了piles[j],分數差值為piles[j] - dp[i][j-1].
所以狀態轉移方程為：
dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])

class solution{public boolean stoneGame(int[] piles) {int dp[][] = new int[piles.length][piles.length] ;for(int i=0;i<piles.length;i++){dp[i][i] = piles[i] ;}for(int j=1;j<piles.length;j++){for(int i=0;i<piles.length-j;i++){dp[i][i+j] = Math.max(piles[i] - dp[i+1][i+j], piles[i+j] - dp[i][i+j-1]) ;}}return dp[0][dp.length-1] > 0 ;}}