394.Coins in a line

1.Description(Medium)

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 thefirstplay will win or lose?

Example

n =1, returntrue.

n =2, returntrue.

n =3, returnfalse.

n =4, returntrue.

n =5, returntrue.

Challenge

O(n) time and O(1) memory

2.Code

https://aaronice.gitbooks.io/lintcode/content/dynamic_programming/coins_in_a_line.html

http://www.cnblogs.com/grandyang/p/5861500.html

Solution 1:

public boolean firstWillWin(int n) {
        return n%3!=0;
    }

Solution 2:

这一个问题可以归类到博弈类问题，需要注意的是博弈有先后手。

• State:

  • 定义一个人的状态: dp[i], 现在还剩i个硬币，现在当前取硬币的人最后输赢状况

• Function:

  • 考虑两个人的状态做状态更新: dp[i] = (!dp[i-1]) || (!dp[i-2])

• Intialize:

  • dp[0] = false

  • dp[1] = true

  • dp[2] = true

• Answer:

  • dp[n]

先思考最小状态 然后思考大的状态 -> 往小的递推，那么非常适合记忆化搜索