Dynamic Programming II

Coin game winner

A and B are playing a game. At the beginning there are n coins. Given two more numbers x and y. In each move a player can pick x or y or 1 coins. A always starts the game. The player who picks the last coin wins the game. For a given value of n, find whether A will win the game or not if both are playing optimally.

Examples:

Input : n = 5, x = 3, y = 4
Output : A

There are 5 coins, every player can pick 1 or 3 or 4 coins on his/her turn. A can win by picking 3 coins in first chance. Now 2 coins will be left so B will pick one coin and now A can win by picking the last coin.

Input : 2 3 4
Output : B

Let us take few example values of n for x = 3, y = 4. n = 0 A can not pick any coin so he losses n = 1 A can pick 1 coin and win the game n = 2 A can pick only 1 coin. Now B will pick 1 coin and win the game n = 3 4 A will win the game by picking 3 or 4 coins n = 5, 6 A will choose 3 or 4 coins. Now B will have to choose from 2 coins so A will win.

We can observe that A wins game for n coins only when it loses for coins n-1, n-x and n-y.

bool findWinner(int x, int y, int n) {
    vector<bool> M(n + 1, false);
    M[1] = true;
    for (int i = 2; i <= n; i++) {
        if (i - 1 >= 0 && M[i - 1] == false) {
            M[i] = true;
        }
        else if (i - x >= 0 && M[i - x] == false) {
            M[i] = true;
        }
        else if (i - y >= 0 && M[i - y] == false) {
            M[i] = true;
        }
        cout << M[i] << endl;
    }
    return M.back();
}

Coin up probablity

有 $n$ 枚硬币，每个硬币掷一次正面朝上的概率各不相同，假定第$i$个概率为$p_i$。如果把所有硬币都掷一次，求 $k$ 个硬币正面朝上的概率。

$M[i][j]$ 抛 j 个硬币有 i 个正面朝上的概率
$M[i][j] = M[i][j-1] *(1 - P[i]) + M[i-1][j-1] * P[i]$
求 $M[n][k]$

Predict the Winner

Leetcode

$M[i][j]$ 表示从index i 到 index j，player 1 比 player 2 取的数的总和多多少。每次取的时候，要么取首个，即为$nums[i]$，那么对手的结果就可以用子问题 $M[i+1][j]$ 来表示，同理取最后一个数。

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> M(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            M[i][i] = nums[i];
        }
        for (int offset = 1; offset < n; offset++) {
            for (int i = 0; i < n - offset; i++) {
                int j = i + offset;
                M[i][j] = max(nums[i] - M[i+1][j], nums[j] - M[i][j-1]);    
            }   
        }
        return M.front().back() >= 0;
    }
};

Can I Win

https://leetcode.com/problems/can-i-win/description/

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        //from 1 to maxChoosableInteger -> ignore position 0
        //state[i] represent the chosen Integer i has been used in the game? t/f 
        string state(maxChoosableInteger + 1, 'f'); 
        unordered_map<string, bool> memo;   //dfs memorization 
        return dfs(maxChoosableInteger, 0, desiredTotal, memo, state);
    }
    
    
    bool dfs(int max, int cur , int target, unordered_map<string, bool> & table, string & state) {
        if (table.count(state)) {
            return table[state];
        }
        for (int i = 1; i <= max; i++) {
            if (state[i] == 'f') {
                state[i] = 't';
                //only if opponent is lost or current chosen number is bigger than target
                //the player win
                if (cur + i >= target || dfs(max, cur + i, target, table, state) == false) {
                    //recover visited state
                    state[i] = 'f';
                    table[state] = true;
                    return true;
                }
                state[i] = 'f';    
            }
        }
        table[state] = false;
        return false;
    }
};