LeetCode–預測玩家
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
486. 預測贏家
題目
給定一個表示分數的非負整數陣列， 玩家 1 從陣列任意一端拿取一個分數，隨后玩家 2 繼續從剩余陣列任意一端拿取分數，然后玩家 1 拿，…… ，每次一個玩家只能拿取一個分數，分數被拿取之后不再可取，直到沒有剩余分數可取時游戲結束，最侄訓得分數總和最多的玩家獲勝，
給定一個表示分數的陣列，預測玩家1是否會成為贏家，你可以假設每個玩家的玩法都會使他的分數最大化，
示例 1：
輸入：[1, 5, 2]
輸出：False
解釋：一開始，玩家1可以從1和2中進行選擇，
如果他選擇 2（或者 1 ），那么玩家 2 可以從 1（或者 2 ）和 5 中進行選擇，如果玩家 2 選擇了 5 ，那么玩家 1 則只剩下 1（或者 2 ）可選，
所以，玩家 1 的最終分數為 1 + 2 = 3，而玩家 2 為 5 ，
因此，玩家 1 永遠不會成為贏家，回傳 False ，
示例 2：
輸入：[1, 5, 233, 7]
輸出：True
解釋：玩家 1 一開始選擇 1 ，然后玩家 2 必須從 5 和 7 中進行選擇，無論玩家 2 選擇了哪個，玩家 1 都可以選擇 233 ，
最終，玩家 1（234 分）比玩家 2（12 分）獲得更多的分數，所以回傳 True，表示玩家 1 可以成為贏家，
提示：
1 <= 給定的陣列長度 <= 20.
陣列里所有分數都為非負數且不會大于 10000000 ，
如果最終兩個玩家的分數相等，那么玩家 1 仍為贏家，
代碼
class Solution {
public boolean PredictTheWinner(int[] nums) {
int length = nums.length;
int[] dp = new int[length];
for(int i = 0;i < length; i++){
dp[i] = nums[i];
}
for(int i = length - 2; i >= 0; i--){
for(int j = i + 1; j < length; j++){
//記錄當前玩家與其他玩家的差值
dp[j] = Math.max(nums[i] - dp[j],nums[j] - dp[j-1]);
}
}
//回傳最后的結果
return dp[length - 1] >= 0;
}
}
感謝
Leetcode
以及勤勞的自己，個人博客，GitHub
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/27410.html
標籤：Java
上一篇：swagger中@ApiModelProperty中example屬性對List的支持
下一篇：List回圈遍歷時移出元素