LintCode: coins in a line I

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定第一个玩家是输还是赢？

n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
n = 4, 返回 true.
n = 5, 返回 true.

解法：DP, 复杂度 O(N), O(N)

最少是n = 3时，返回false，说明当一个player面临只有3个棋子的时候，他肯定会输。
dp[i]表示的是，当有i个棋子的时候，先手玩家会不会输。dp[i]这个状态可以由dp[i - 1]或者dp[i - 2]跳过来。dp[i]赢得条件是，dp[i - 1]和dp[i - 2]的状态是输的状态。

可以优化空间复杂度到O(1)。

Java:

public boolean firstWillWin(int n) {

    boolean[] dp = new boolean[n + 1];

    for(int i = 1; i <= n; i ++) {

        if(i == 1 || i == 2) dp[i] = true;

        else dp[i] = !dp[i - 1] || !dp[i - 2];

    }

    return dp[n];

}

类似题目：

[LintCode] Coins in a line II

巴特西

LintCode: coins in a line I

最新文章

热门文章