LintCode刷题——硬币排成线I、II

硬币排成线I：

题目描述：

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定第一个玩家是输还是赢？

样例：

n = 1, 返回 true.

n = 2, 返回 true.

n = 3, 返回 false.

n = 4, 返回 true.

n = 5, 返回 true.

挑战：

O(1) 时间复杂度且O(1) 存储。

算法分析：

本题一个人可以拿1个或者2个，如果输入的n符合条件，为了确保第一个人拿一定能够赢，则对拿法一定要有要求：第一个人在第一次拿之后一定要保证剩下的物品数量为3的倍数，接下来无论第二个人怎么拿，第一个人还是能把剩下的物品数量控制在3的倍数，因此第一个人一定能够确保自己拿到最后一枚硬币并获胜。因此对于输入的数n，n%3=0时为false，否则为true；

代码（应当是LintCode的最简代码了吧）：

public class Solution {
    /*
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        // write your code here
        return n%3!=0;
    }
}

硬币排成线II：

题目描述：

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。

请判定第一个玩家是输还是赢？

样例：

给定数组 A = [1,2,2], 返回 true.

给定数组 A = [1,2,4], 返回 false.

算法描述：

对于本题，其判断输赢的标准是拿到硬币总价值的高低，有两种解法：动态规划或者递归遍历出所有情况并判断每种情况。然而，对于递归实现我觉得是比较无脑且费时的，而且对于本题一定会TLE。

这里介绍一下动态规划的解法：

①要判断第一个玩家是否能够赢得比赛，我们就需要对玩家的不同拿法进行分析与判断，得到利润最大的那种拿法。因为针对玩家1的每一种拿法，玩家2会想出自己的拿法让玩家1接下去的获利最小，而对玩家1，就是要保证当前的拿法能够使剩下的硬币获利最大，因此我们需要从后往前通过记录后续拿法的最优解来进行动态规划。

②建立数组DP[i]表示拿第i个硬币到第n个硬币所能获得的最大利润；

③对于玩家拿到第i个硬币时，玩家拿硬币仍是从左往右拿。因此他有两种选择，仅拿第i个硬币或者拿第i个与第i+1个硬币，这两种拿法均会产生一个价值作为DP[i]的值；因为我们是从后往前进行动态规划，我们知道后续的结果，因此我们知道怎样的拿法会使得最终结果更好；

④第二个玩家在我们做出选择后也会对第一个玩家的利益进行限制，例如当第一个玩家拿第i个硬币时，他可以拿第i+1个或拿第i+1、i+2个硬币，但是他会对的结果进行判断，保证第一个玩家的获利达到最小，即选择DP[i+2]和DP[i+3]中的最小值来决定自己是拿一个还是拿两个；

综上，动态规划表达式为：DP[i] = max{nums[i]+min{DP[i+2],DP[i+3]} ,  nums[i]+nums[i+1]+min{DP[i+3],DP[i+4]} };

代码：

public class Solution {
    /*
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        // write your code here
        int n = values.length;
        if(values==null||n==0){
            return false;
        }
        if(n<=2){
            return true;
        }
        int[] DP = new int[n+1];
        DP[n]=0;
        DP[n-1]=values[n-1];
        DP[n-2]=values[n-1]+values[n-2];
        DP[n-3]=values[n-2]+values[n-3];
        for(int i=n-4;i>=0;i--){
            //我们取一个数或取两个数
            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]));
        }
        int sum=0;
        for(int i:values){
            sum+=i;
        }
        return DP[0]*2>sum;
    }
}