【題目描述】
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?
有?n?個(gè)硬幣排成一條線闸翅。兩個(gè)參賽者輪流從右邊依次拿走 1 或 2 個(gè)硬幣网棍，直到?jīng)]有硬幣為止置媳。拿到最后一枚硬幣的人獲勝。
請(qǐng)判定?第一個(gè)玩家?是輸還是贏？
【題目鏈接】
www.lintcode.com/en/problem/coins-in-a-line/
【題目解析】
其實(shí)此問(wèn)題如果從另一個(gè)角度思考，就是從最后剩余1個(gè)或2個(gè)硬幣時(shí)進(jìn)行倒推，尋找規(guī)律：
先手輸：
o o o | o o o
先手勝：
o | o o o
制勝的方法就是一定在倒數(shù)第二個(gè)回合時(shí)帜慢，讓對(duì)手面對(duì)3個(gè)硬幣，這樣因?yàn)樽约嚎梢阅?或者2個(gè)硬幣，那么無(wú)論對(duì)手選1個(gè)或者2個(gè)粱玲，己方都可以拿到最后一個(gè)硬幣躬柬。這個(gè)規(guī)律就是每次讓對(duì)手都面對(duì)3的倍數(shù)個(gè)硬幣，那么無(wú)論對(duì)方取1個(gè)或者2個(gè)抽减，只需要取相應(yīng)的硬幣數(shù)允青，讓剩下的硬幣數(shù)目保持3X，這樣就能夠保證取勝卵沉。對(duì)于先手而言颠锉，如果自己第一輪面對(duì)的就是3的倍數(shù)個(gè)硬幣，那么對(duì)手則可以使用同樣的策略讓自己一方每次面對(duì)3X個(gè)硬幣史汗。于是先手是否獲勝的唯一要素就是初始硬幣數(shù)目琼掠，在不為3的整數(shù)倍情況下，先手都可以獲勝停撞。這樣的話瓷蛙，算法時(shí)間復(fù)雜度和空間復(fù)雜度都為O(1)。
【參考答案】
