Coins Problem Set C++ Solution


  • 1
    F

    Coins in a line 1

    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?

    class Solution {
    public:
        /**
         * @param n: an integer
         * @return: a boolean which equals to true if the first player will win
         */
         bool firstWillWin(int n) {
            if(n == 0)  return false;
            vector<bool> dp(n + 1, false);
            // dp[i] = true, the i th coin is fetched by player i
            // dp[i] = false, the i th coin is fetched by player i
            dp[0] = false;
            dp[1] = true;
            for(int i = 2; i <= n; i++) {
                dp[i] = (!dp[i-2] || !dp[i-1]);
            }
            return dp[n];
        }
    };
    
    

    Coins in a line 2

    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?

    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
            /**
             * 
             * dp[i][j] = max(values[i] + sums[i+1][j] - dp[i+1][j], 
             *                values[i] + values[i+1] + sum[i+2][j] - dp[i+2][j])
             * 
             *  <=======>
             * 
             * dp[i][j] = sums[i][j] - min(dp[i+1][j], dp[i+2][j]);
             * 
             **/
            int size_ = values.size();
            vector<vector<int>> dp(size_, vector<int>(size_, 0));
            vector<vector<int>> sums(size_, vector<int>(size_, 0));
            
            for(int i = 0; i < size_; i++) {
                for(int j = i; j < size_; j++) {
                    if(i == j)  sums[i][j] = values[i];
                    else {
                        sums[i][j] = sums[i][j-1] + values[j];
                    }
                }
            }
            
            for (int i = size_ - 1; i >= 0; i--) {
                for (int j = i; j < size_; j++) {
                    if(i == j) {
                        dp[i][j] = sums[i][j];
                    }
                    else if(i + 1 == j) {
                        dp[i][j] = max(values[i], values[j]);
                    }
                    else {
                        dp[i][j] = sums[i][j] - min(dp[i+1][j], dp[i+2][j]);
                        // if(i + 2 < size_)
                        //     dp[i][j] = sums[i][j] - min(dp[i+1][j], dp[i+2][j]);
                        // else {
                        //     dp[i][j] = max(values[i], values[j]);
                        // }
                    }
                }
            }
            
            return dp[0][size_-1] > sums[0][size_-1] - dp[0][size_-1];
        }
    };
    

    Coins in a line 3

    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?

    dp题,主要是要推导出公式:
    dp[i][j]=max(A[i]+sum[i+1][j]-dp[i+1][j], A[j]+sum[i][j-1]-dp[i][j-1])
    A[i]+sum[i+1][j] 和 A[j]+sum[i][j-1]都等于sum[i][j],因此最后公式成为:
    dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])
    比较特别的dp题。game theory。

    class Solution {
    	bool first_win(vector<int> values) {
    		int size = static_cast<int>(values.size());
    		if (size <= 1) return true;
    		int store[size][size];
    		int sum[size][size];
    		for (int i = 0; i < size; i++) {
    			for (int j = i; j < size; j++) {
    				sum[i][j] = i == j ? values[j] : sum[i][j-1] + values[j];
    			}
    		}
    		for (int i = size - 1; i >= 0; i--) {
    			for (int j = i; j < size; j++) {
    				if (i == j) store[i][j] = values[i];
    				else {
    					int cur = min(store[i+1][j], store[i][j-1]);
    					store[i][j] = store[i][j] - cur;
    				}
    			}
    		}
    		return store[0][size-1] > sum[0][size-1] - store[0][size-1];
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.