資訊專欄INFORMATION COLUMN
摘要：兩個(gè)參賽者輪流從左邊依次拿走或個(gè)硬幣，直到?jīng)]有硬幣為止。計(jì)算兩個(gè)人分別拿到的硬幣總價(jià)值，價(jià)值高的人獲勝。請(qǐng)判定第一個(gè)玩家是輸還是贏樣例給定數(shù)組返回給定數(shù)組返回復(fù)雜度思路考慮先手玩家在狀態(tài)，表示在在第的硬幣的時(shí)候，這一位玩家能拿到的最高價(jià)值。
LintCode Coins in a line II
dp有 n 個(gè)不同價(jià)值的硬幣排成一條線。兩個(gè)參賽者輪流從左邊依次拿走 1 或 2 個(gè)硬幣，直到?jīng)]有硬幣為止。計(jì)算兩個(gè)人分別拿到的硬幣總價(jià)值，價(jià)值高的人獲勝。
請(qǐng)判定 第一個(gè)玩家 是輸還是贏？
樣例
給定數(shù)組 A = [1,2,2], 返回 true.
給定數(shù)組 A = [1,2,4], 返回 false.
復(fù)雜度
O(N)
思路
考慮先手玩家在狀態(tài)dp[i]，dp[i]表示在在第i的硬幣的時(shí)候，這一位玩家能拿到的最高價(jià)值。
如果先手玩家取一枚硬幣，那么dp[i] = values[i] + sum[i + 1] - dp[i + 1]。減去dp[i + 1]的原因是，對(duì)手玩家，每次也要想辦法拿到最大的價(jià)值，所以先手玩家能拿到的價(jià)值是在對(duì)手玩家拿到最大價(jià)值的硬幣之后的剩余的硬幣價(jià)值。
如果先手玩家取兩枚，那么dp[i] = values[i] + values[i + 1] + sum[i + 2] - dp[i + 2];
注意判斷是否先手玩家贏的條件，是2倍dp[0]的值是不是大于sum[0]，應(yīng)為是要求拿到硬幣價(jià)值多的玩家算贏。
代碼
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
復(fù)雜度
O(N),O(N)
思路
思路是一樣，不過是從bottom-up的算法，用map來保存已經(jīng)搜索過的路線。
代碼
