lintcode 394+395 游戏博弈

lintcode 394

• 解题思路： dp
  dp[i]:代表面对i个石子，是否先手必赢。
  dp[i]=(dp[i-1]==false)||(dp[i-2]==false);

  
  图片.png

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

lintcode 395

dp[i]: 面对values[i......n-1] 能得到最大的数字差
dp[i]=max(values[i]-dp[i+1],values[i]+values[i+1]-dp[i+2]);

图片.png

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) {
        if(values.empty())
        return true;
        int m=values.size();
        vector<int> dp(m+1,false);
        dp[m]=0;
        for(int i=m-1;i>=0;i--){
            dp[i]=values[i]-dp[i+1];
            if(i<m-1)//not the first one
                dp[i]=max(dp[i],values[i]+values[i+1]-dp[i+2]);
        }
        return dp[0]>=0;
    }
};