# Coins in a Line

## Question

There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left. The player who take the last coin wins.
Could you please decide the first play will win or lose?
Example
n = 1, return true.
n = 2, return true.
n = 3, return false.
n = 4, return true.
n = 5, return true.
Challenge
O(n) time and O(1) memory
Tags
Greedy Dynamic Programming Array Game Theory
Related Problems
Hard Coins in a Line III 30 % Medium Coins in a Line II

## Analysis

### Dynamic Programming

• State:
• 定义一个人的状态: dp[i], 现在还剩i个硬币，现在当前取硬币的人最后输赢状况
• Function:
• 考虑两个人的状态做状态更新: dp[i] = (!dp[i-1]) || (!dp[i-2])
• Intialize:
• dp[0] = false
• dp[1] = true
• dp[2] = true
• dp[n]

o o o | o o o

o | o o o

## Solution

StackOverflow
public class Solution {
/**
* @param n: an integer
* @return: a boolean which equals to true if the first player will win
*/
public boolean firstWillWin(int n) {
boolean[] dp = new boolean[n + 1];
boolean[] flag = new boolean[n + 1];
return search(n, dp, flag);
}
boolean search(int i, boolean[] dp, boolean[] flag) {
if (flag[i] == true) {
return dp[i];
}
if (i == 0) {
dp[i] = false;
} else if (i == 1) {
dp[i] = true;
} else if (i == 2) {
dp[i] = true;
} else {
dp[i] = ! (search(i - 1, dp, flag) && search(i - 2, dp, flag));
}
flag[i] = true;
return dp[i];
}
}
Improved
public class Solution {
/**
* @param n: an integer
* @return: a boolean which equals to true if the first player will win
*/
public boolean firstWillWin(int n) {
int []dp = new int[n+1];
return MemorySearch(n, dp);
}
boolean MemorySearch(int n, int []dp) { // 0 is empty, 1 is false, 2 is true
if(dp[n] != 0) {
if(dp[n] == 1)
return false;
else
return true;
}
if(n <= 0) {
dp[n] = 1;
} else if(n == 1) {
dp[n] = 2;
} else if(n == 2) {
dp[n] = 2;
} else if(n == 3) {
dp[n] = 1;
} else {
if((MemorySearch(n-2, dp) && MemorySearch(n-3, dp)) ||
(MemorySearch(n-3, dp) && MemorySearch(n-4, dp) )) {
dp[n] = 2;
} else {
dp[n] = 1;
}
}
if(dp[n] == 2)
return true;
return false;
}
}
N % 3 - Time O(1), Space O(1)
public class Solution {
/**
* @param n: an integer
* @return: a boolean which equals to true if the first player will win
*/
public boolean firstWillWin(int n) {
if (n % 3 == 0) {
return false;
}
return true;
}
}