題目
有 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.
分析
這道題運(yùn)用動(dòng)態(tài)規(guī)劃來解決缩搅。
dp[i] 表示從i到end 能拿到的最大值
一個(gè)明顯的情況就是當(dāng)len<=2時(shí)触幼，這時(shí)候第一個(gè)拿的只要全拿走就行了，所以肯定是第一個(gè)人贏巨双。然后我們分析
- 當(dāng)i=len的時(shí)候霉祸，dp[len]沒得可拿，所以dp[len]=0
- 當(dāng)i=len-1的時(shí)候慢宗，dp[len-1]只有一個(gè)可以拿奔穿，所以dp[len-1] = values[len-1];
- 當(dāng)i = len-2的時(shí)候，dp[len-2]有兩個(gè)可拿缅茉，當(dāng)然是直接拿走,所以dp[len-2] = values[len-1]+values[len-2];
- 當(dāng)i=len-3的時(shí)候男摧，剩下最后三個(gè)，這時(shí)候如果拿一個(gè)拇颅，對(duì)方就會(huì)拿走兩個(gè)乔询，所以，這次要拿兩個(gè)黄锤，所以dp[len-3] = values[len-2]+ values[len-3];
- 當(dāng)i = len-4以及以后的情況中，顯然可以選擇拿一個(gè)或者拿兩個(gè)兩種情況勉吻，我們自然是選擇拿最多的那個(gè)作為dp的值旅赢，那么我們就分分析這兩種情況：
第一種，只拿一個(gè),那么對(duì)手可能拿兩個(gè)或者一個(gè)短纵，對(duì)手肯定是盡可能多拿僵控，所以我們要選擇盡可能小的那個(gè)，所以dp[i] = values[i] + min(dp[i+2],dp[i+3])
第二種悠就，拿兩個(gè)充易，同樣的情況，dp[i] = values[i]+ values[i+1]+min(dp[i+3],dp[i+4])
然后我們?nèi)∵@兩種情況下的最大值炸茧。
代碼
public class Solution {
/**
* @param values: an array of integers
* @return: a boolean which equals to true if the first player will win
*/
public boolean firstWillWin(int[] values) {
// write your code here
// dp 表示從i到end 的最大值
// int values[] ={1,2,4,3,4,8,5,6,12};
int len = values.length;
int[] dp = new int[len+1];
if(len<=2)
return true;
dp[len] = 0;
dp[len-1] = values[len-1];
dp[len-2] = values[len-2] + values[len-1];
dp[len-3] = values[len-3] + values[len-2];
for(int i = len-4;i>=0;i--) {
dp[i] = Math.max(values[i]+Math.min(dp[i+2],dp[i+3]), values[i]+values[i+1]+Math.min(dp[i+3], dp[i+4]));
}
int sum=0;
for(int a:values)
sum+=a;
return dp[0] > sum-dp[0];
}
}
