描述
有 n 個不同價值的硬幣排成一條線，兩個參賽者輪流從 左邊 依次拿走 1 或 2 個硬幣，直到沒有硬幣為止，計算兩個人分別拿到的硬幣總價值，價值高的人獲勝，
請判定 先手玩家 必勝還是必敗?
若必勝, 回傳 true, 否則回傳 false.
樣例
- 樣例 1:
輸入: [1, 2, 2]
輸出: true
解釋: 先手玩家直接拿走兩顆硬幣即可.
- 樣例 2:
輸入: [1, 2, 4]
輸出: false
解釋: 無論先手拿一個還是兩個, 后手可以拿完, 然后總價值更高.
決議
firstWillWin = function (values) {
n = values.length;
f = [];
f[n] = 0; // 0 coins left
f[n - 1] = values[n - 1]; // only last coin left
for (i = n - 2; i >= 0; i--){
f[i] = Math.max(values[i] - f[i + 1], values[i] + values[i + 1] - f[i + 2]);
}
return f[0] >=0;
}
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/77121.html
標籤：其他
上一篇：unity 音樂小游戲
下一篇：c語言寫掃雷新手詳解