题目
有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。
请判定 第一个玩家 是输还是赢？
样例
n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
n = 4, 返回 true.
n = 5, 返回 true.
挑战
Java Code
O(1) 时间复杂度且O(1) 存储。
解题
两个人在一次拿的时候，当第一个人拿的是1 时，第二个人拿的就是2；当第一个人拿的是2时，第二个人拿的就是1。这样一次拿取得值是3.这样就是一个以3为周期的序列，当只剩三个硬币的时候，不傻也知道怎么拿的。如下，直接对只有三枚硬币的情况考虑即可。
n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
注意：
取硬币格式的序列可以是：（1,2）,（1,2）,（2,1），（1,2）而不是严格的按照（1,2）（1,2）的序列取硬币
解题
根据上面给的样例，很简单的写出下面程序了
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) { // write your code here return n%3!=0; }} 当然也可以递归的
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) { // write your code here if(n==1||n==2) return true; if(n==0 ||n==3) return false; return firstWillWin(n-3); }} 法二
根据上面的程序，感觉是直接推出来的规律
| 第2个人 | 第1个人 | |
| 1 | F | T |
| 2 | F | T |
| 3 | T | F |
| 4 | F | T |
| 5 | F | T |
| 6 | T | F |
| 7 | F | T |
| 8 | F | T |
| 9 | T | F |
当 n大于3的时候
对第0列，也就是第二个人的结果是：D[i][0] = D[i-1][1] && D[i-2][1]
对第1列，也就是第一个人的结果是：D[i][0] = D[i-1][0] || D[i-2][0]
说明当前人能否获胜收到另外一个人连续两次取值的影响，与上面通过找规律的结果其实也是一样的。
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) { // write your code here if( n <=0 ) return false; if(n <=2 ) return true; boolean [][] D = new boolean[n+1][2]; D[1][1] = true; D[2][1] = true; D[1][0] = false; D[2][0] = false; for(int i = 3 ;i<= n ;i++){ for( int j = 0;j<=1;j++){ if( j==1 ){ D[i][j] = D[i-1][1-j] || D[i-2][1-j]; }else{ D[i][j] = D[i-1][1-j] && D[i-2][1-j]; } } } return D[n][1]; }} 总耗时: 807 ms