lintcode 394. Coins in a Line 、leetcode 292. Nim Game 、lintcode 395. Coins in a Line II

變型：如果是最後拿走所有石子那個人輸，則f[0] = true

394. Coins in a Line

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];
    }
};      

292. Nim Game

這個題幾乎與Coins in a Line一模一樣。

解法一：

這個解法超記憶體了

class Solution {
public:
    bool canWinNim(int n) {
        if(n == 0)
            return false;
        if(n == 1 || n == 2)
            return true;
        vector<int> dp(n+1);
        dp[0] = false,dp[1] = true,dp[2] = true;
        for(int i = 3;i <= n;i++){
            if(dp[i-1] == true && dp[i-2] == true && dp[i-3] == true)
                dp[i] = false;
            else if(dp[i-1] == false && dp[i-2] == false && dp[i-3] == false)
                dp[i] = true;
            else
                dp[i] = true;
        }
        return dp[n];
    }
};      

解法二：

因為隻與前3個有關系，是以用變量替代，能不超記憶體，但逾時了

class Solution {
public:
    bool canWinNim(int n) {
        if(n == 0)
            return false;
        if(n == 1 || n == 2)
            return true;
        bool num1 = false,num2 = true,num3 = true;
        for(int i = 3;i <= n;i++){
            bool tmp;
            if(num1 == true && num2 == true && num3 == true){
                tmp = false;
            }
            else
                tmp = true;
            num1 = num2;
            num2 = num3;
            num3 = tmp;
        }
        return num3;
    }
};      

解法三：

過

class Solution {
public:
    bool canWinNim(int n) {
        return n%4 ? true : false;
    }
};      

395. Coins in a Line II 

與Coins in a Line相同的是，這個題每次也隻能拿一個或者兩個。不同的是，最終的勝負是誰擁有的金币的價值更多。

dp[i]表示從i到end可取的最大錢數

如果取一個，dp[i] = values[i] + min(dp[i+2],dp[i+3])

如果取兩個，dp[i] = values[i] + values[i+1] + min(dp[i+3],dp[i+4])

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int n = values.size();
        if(n <= 2)
            return true;
        vector<int> dp(n+1,0);
        dp[n-1] = values[n-1];
        dp[n-2] = values[n-2] + values[n-1];
        dp[n-3] = values[n-3] + values[n-2];
        for(int i = n - 4;i >= 0;i--)
            dp[i] = max(values[i] + min(dp[i+2],dp[i+3]),values[i] + values[i+1] + min(dp[i+3],dp[i+4]));
        int sum = 0;
        for(int i = 0;i < n;i++)
            sum += values[i];
        return dp[0] > sum - dp[0];
    }
};