[LintCode] Coins in a Line I & II

java 4 2016-02-29 13:03
女装

Coins in a Line I Solution

第一个游戏者永远拿不到第3n枚硬币,所以在硬币总数不能被3整除的情况下,都可以赢。

public class Solution {
    public boolean firstWillWin(int n) {
        return n % 3 != 0; 
    }
}

Coins in a Line II

Problem

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?

Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

Note

自己想的第一种方法,假设第二个游戏者采用极端情况,只取第“3的倍数”枚硬币,即A[2], A[5], A[8], A[11]...然后对这些硬币的价值求和,再和所有硬币的价值之和的一半比,因为另一半的价值被第一个游戏者获得。
DP做法,设dp[i]为第一个游戏者从第i枚硬币到end能获得硬币价值的最大值。

Solution

Muggle method

public class Solution {
    public boolean firstWillWin(int[] A) {
        // write your code here
        if (A == null) return false;
        int sum = 0;
        for (int i = 1; i <= A.length / 3; i++) {
            sum += A[3*i-1];
        }
        int total = 0;
        for (int i = 0; i < A.length; i++) {
            total += A[i];
        }
        if (sum * 2 > total) return false;
        return true;
    }
}

DP method

主要参考这篇文章的解释

http://www.mamicode.com/info-detail-1114851.html

public class Solution {
    public boolean firstWillWin(int[] values) {
        // write your code here
        int len = values.length;
        if (len <= 2) {
            return true;
        }
        //dp[i] means the largest value you(the first player) 
        //can get when you start from values[i] 
        int[] dp = new int[len+1];
        //not even exist
        dp[len] = 0;
        //when you happen to have the last coin, yes, consider the last first
        dp[len-1] = values[len-1];
        //sure we should get the last two for most value
        dp[len-2] = values[len-1] + values[len-2];
        //same rules, why leave two(len-1, len-2) for the other player
        dp[len-3] = values[len-2] + values[len-3];
        //next we are gonna sum up
        for (int i = len-4; i >= 0; i--) {
            //you have to have values[i] and the non-optimal later choice
            //because the other player is smart to leave you the worse one
            //between two of your optimal choices
            dp[i] = values[i] + Math.min(dp[i+2], dp[i+3]);
            dp[i] = Math.max(dp[i], values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));
            //equals to: dp[i] = Math.max(values[i] + Math.min(dp[i+2],dp[i+3]), values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));
        }
        //compute the total value of coins
        int sum = 0;
        for (int a: values) {
            sum += a;   
        }
        //compare your final value to the other player's
        return dp[0] > sum - dp[0];
    }
}
女装
文章评论