Coins in a Line 1

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.

思路： dp[i]代表i个硬币是能不能赢，所以递推公式是 dp[i] = (!dp[i-1]) or (!dp[i-2])。 而i个的硬币能赢代表i-1个硬币，i-2个硬币时，你的对手都不能赢。反着想一下，从递推的公式可以看出，由i和i+1能够推出i+2的结果。所以一个for loop搞定。

http://www.lintcode.com/en/problem/coins-in-a-line/

class Solution(object):
    def coin1(self, n):
        if n==0:
            return False
        if n==1 or n==2:
            return True

        dp = [1, 1]
        for i in range(2, n):
            # play can win only when dp[-1] and dp[-2] can't win.
            if not dp[-1] or not dp[-2]:
                new = 1
            else:
                new = 0
            dp.append(new)

        return dp[-1]==1

so = Solution()
print so.coin1(6)