資訊專欄INFORMATION COLUMN
摘要：兩個參賽者輪流從左邊依次拿走或個硬幣，直到沒有硬幣為止。計算兩個人分別拿到的硬幣總價值，價值高的人獲勝。請判定第一個玩家是輸還是贏樣例給定數組返回給定數組返回復雜度思路考慮先手玩家在狀態，表示在在第的硬幣的時候，這一位玩家能拿到的最高價值。
LintCode Coins in a line II
dp有 n 個不同價值的硬幣排成一條線。兩個參賽者輪流從左邊依次拿走 1 或 2 個硬幣，直到沒有硬幣為止。計算兩個人分別拿到的硬幣總價值，價值高的人獲勝。
請判定 第一個玩家 是輸還是贏？
樣例
給定數組 A = [1,2,2], 返回 true.
給定數組 A = [1,2,4], 返回 false.
復雜度
O(N)
思路
考慮先手玩家在狀態dp[i]，dp[i]表示在在第i的硬幣的時候，這一位玩家能拿到的最高價值。
如果先手玩家取一枚硬幣，那么dp[i] = values[i] + sum[i + 1] - dp[i + 1]。減去dp[i + 1]的原因是，對手玩家，每次也要想辦法拿到最大的價值，所以先手玩家能拿到的價值是在對手玩家拿到最大價值的硬幣之后的剩余的硬幣價值。
如果先手玩家取兩枚，那么dp[i] = values[i] + values[i + 1] + sum[i + 2] - dp[i + 2];
注意判斷是否先手玩家贏的條件，是2倍dp[0]的值是不是大于sum[0]，應為是要求拿到硬幣價值多的玩家算贏。
代碼
public boolean firstWillWin(int[] values) {
int len = values.length;
int[] sum = new int[len];
int[] dp = new int[len];
for(int i = len - 1; i >= 0; i --) {
if(i == len - 1) sum[i] = values[i];
else sum[i] = values[i] + sum[i + 1];
}
for(int i = len - 1; i >= 0; i --) {
if(i == len - 1) dp[i] = values[i];
else if(i == len - 2) dp[i] = values[i] + values[i + 1];
else {
dp[i] = Math.max(values[i] + sum[i + 1] - dp[i + 1], values[i] + values[i + 2] + sum[i + 2] - dp[i + 2]);
}
}
return dp[0] * 2 > sum[0];
}
Recursion + Memorization
復雜度
O(N),O(N)
思路
思路是一樣，不過是從bottom-up的算法，用map來保存已經搜索過的路線。
代碼
