lintcode 394. Coins in a Line

佚名 6年前 (2019-05-07) 随笔 1214人围观抢沙发百度已收录

变型：如果是最后拿走所有石子那个人输，则f[0] = true

394. Coins in a Line

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

dp[n]表示n个石子，先手的人，是必胜还是必输。拿1个石子，2个石子之后都是必胜，则当前必败；拿1个石子，2个石子之后都是必败，则当前必胜；如果拿1个石子，2个石子之后有必败，则当前必胜。

class Solution {
public:
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    bool firstWillWin(int n) {
        // write your code here
        if(n == 0)
            return false;
        if(n == 1)
            return true;
        vector<int> dp(n+1);
        dp[0] = false,dp[1] = true;
        for(int i = 2;i <= n;i++){
            if(dp[i-1] == true && dp[i-2] == true)
                dp[i] = false;
            else if(dp[i-1] == false && dp[i-2] == false)
                dp[i] = true;
            else
                dp[i] = dp[i-1] || dp[i-2];
        }
        return dp[n];
    }
};