|
| 1 | +/** |
| 2 | + * Alex and Lee play a game with piles of stones. There are an even number of |
| 3 | + * piles arranged in a row, and each pile has a positive integer number of |
| 4 | + * stones piles[i]. |
| 5 | + * |
| 6 | + * The objective of the game is to end with the most stones. The total number |
| 7 | + * of stones is odd, so there are no ties. |
| 8 | + * |
| 9 | + * Alex and Lee take turns, with Alex starting first. Each turn, a player |
| 10 | + * takes the entire pile of stones from either the beginning or the end of the |
| 11 | + * row. This continues until there are no more piles left, at which point the |
| 12 | + * person with the most stones wins. |
| 13 | + * |
| 14 | + * Assuming Alex and Lee play optimally, return True if and only if Alex wins |
| 15 | + * the game. |
| 16 | + * |
| 17 | + * Example 1: |
| 18 | + * |
| 19 | + * Input: [5,3,4,5] |
| 20 | + * Output: true |
| 21 | + * Explanation: |
| 22 | + * Alex starts first, and can only take the first 5 or the last 5. |
| 23 | + * Say he takes the first 5, so that the row becomes [3, 4, 5]. |
| 24 | + * If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points. |
| 25 | + * If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points. |
| 26 | + * This demonstrated that taking the first 5 was a winning move for Alex, so we return true. |
| 27 | + * |
| 28 | + * Note: |
| 29 | + * 2 <= piles.length <= 500 |
| 30 | + * piles.length is even. |
| 31 | + * 1 <= piles[i] <= 500 |
| 32 | + * sum(piles) is odd. |
| 33 | + */ |
| 34 | + |
| 35 | +publicclassStoneGame877 { |
| 36 | +publicbooleanstoneGame(int[]piles) { |
| 37 | +intN =piles.length; |
| 38 | +returnstoneGame(piles,0,N-1,true,0,0); |
| 39 | + } |
| 40 | + |
| 41 | +publicbooleanstoneGame(int[]piles,inti,intj,booleanA,intsumA,intsumL) { |
| 42 | +if (i >j)returnsumA >sumL; |
| 43 | +if (A) { |
| 44 | +returnstoneGame(piles,i+1,j,true,sumA+piles[i],sumL) ||stoneGame(piles,i,j-1,true,sumA,sumL+piles[j]); |
| 45 | + } |
| 46 | +returnstoneGame(piles,i+1,j,true,sumA+piles[i],sumL) &&stoneGame(piles,i,j-1,true,sumA,sumL+piles[j]); |
| 47 | + } |
| 48 | + |
| 49 | +/** |
| 50 | + * :D |
| 51 | + */ |
| 52 | +publicbooleanstoneGame2(int[]piles) { |
| 53 | +returntrue; |
| 54 | + } |
| 55 | + |
| 56 | +} |