MinMax

Coins in a Line

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?

Example

n = 1, return true.
n = 2, return true.
n = 3, return false.
n = 4, return true.
n = 5, return true.

     bool firstWillWin(int n) {
        if (n <= 0) return false;
        if (n < 3) return true;
        vector<bool> dp(n+1);
        dp[0] = false;
        dp[1] = true;
        dp[2] = true;

        for (int i = 3; i <= n; ++i) {
            dp[i] = !(dp[i-1] && dp[i-2]);
        }

        return dp[n];
    }

Coins in a Line II

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide the first player will win or lose?

bool firstWillWin(vector<int> &values) {
    size_t n = values.size();
    if (n == 0) return false;
    vector<int> dp(n+1);
    if (n < 3) return true;
    dp[1] = values[n-1];
    dp[2] = values[n-1] + values[n-2];
    dp[3] = valude[n-2] + values[n-3];
    for (int i = 4; i <= n; ++i) {
        int pick_one = min(dp[i-2], dp[i-3]) + values[n - i];
        int pick_two = min(dp[i-3], dp[i-4]) + values[n - i] + values[n-i+1];
        dp[i] = max(pick_one, pick_two);
    }
    return (dp[n] > dp[n-1] || dp[n] > dp[n-2]);
}

Coins in a Line III

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

bool firstWillWin(vector<int> &values) {
    size_t n = values.size();
    if (n < 2) return true;
    vector<vector<int>> dp(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        dp[i][i] = values[i];
        if (i < n -1) dp[i][i+1] = max(values[i], values[i+1]);
    }

    for (int l = 2; l <= n; ++l) {
        for (int i = 0; i + l < n; ++i) {
            int j = i + l;
            dp[i][j] = max(values[i] + min(dp[i+2][j], dp[i+1][j-1]), values[j] + min(dp[i][j-2], dp[i+1][j-1]));
        }
    }
    if (dp[0][n-1] > dp[1][n-1] || dp[0][n-1] > dp[0][n-2]) return true;
    return false;
}

294 Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm's runtime complexity.

class Solution {
public:
    bool canWin(string s) {
        if (s.size() < 2) return false;
        bool canwin = can_win(s);
        return canwin;
    }

    bool can_win(string& s) {
        for (size_t i = 1; i < s.size(); i++) {
            if (s[i-1] == '+' && s[i] == '+') {
                s[i-1] = '-';
                s[i] = '-';
                bool wins = !can_win(s);
                s[i-1] = '+';
                s[i] = '+';
                if (wins) return true;
            }
        }
        return false;
    }
};