Massive Algorithms: LintCode 395

LintCode 395 - Coins in a Line II

Techinpad: [LintCode] 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?

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

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

http://www.cnblogs.com/grandyang/p/5864323.html

这道题是之前那道Coins in a Line的延伸，由于每个硬币的面值不同，所以那道题的数学解法就不行了，这里我们需要使用一种方法叫做极小化极大算法Minimax，这是博弈论中比较经典的一种思想，LeetCode上有一道需要用这种思路解的题Guess Number Higher or Lower II。这道题如果没有接触过相类似的题，感觉还是蛮有难度的。我们需要用DP来解，我们定义一个一维数组dp，其中dp[i]表示从i到end可取的最大钱数，大小比values数组多出一位，若n为values的长度，那么dp[n]先初始化为0。我们是从后往前推，我们想如果是values数组的最后一位，及i = n-1时，此时dp[n-1]应该初始化为values[n-1]，因为拿了肯定比不拿大，钱又没有负面额；那么继续往前推，当i=n-2时，dp[n-2]应该初始化为values[n-2]+values[n-1]，应为最多可以拿两个，所以最大值肯定是两个都拿；当i=n-3时，dp[n-3]应该初始化为values[n-3]+values[n-2]，因为此时还剩三个硬币，你若只拿一个，那么就会给对手留两个，当然不行，所以自己要拿两个，只能给对手留一个，那么到目前位置初始化的步骤就完成了，下面就需要找递推式了：

当我们处在i处时，我们有两种选择，拿一个还是拿两个硬币，我们现在分情况讨论：

1. 当我们只拿一个硬币values[i]时，那么对手有两种选择，拿一个硬币values[i+1]，或者拿两个硬币values[i+1] + values[i+2]
a) 当对手只拿一个硬币values[i+1]时，我们只能从i+2到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+2]
b) 当对手拿两个硬币values[i+1] + values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3]
由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+2]和dp[i+3]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + min(dp[i+2], dp[i+3])

2. 当我们拿两个硬币values[i] + values[i + 1]时，那么对手有两种选择，拿一个硬币values[i+2]，或者拿两个硬币values[i+2] + values[i+3]
a) 当对手只拿一个硬币values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3]
b) 当对手拿两个硬币values[i+2] + values[i+3]时，我们只能从i+4到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+4]
由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+3]和dp[i+4]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + values[i + 1] + min(dp[i+3], dp[i+4])

综上所述，递推式就有了 dp[i] = max(values[i] + min(dp[i+2], dp[i+3]), values[i] + values[i + 1] + min(dp[i+3], dp[i+4]))
这样当我们算出了dp[0]，知道了第一个玩家能取出的最大钱数，我们只需要算出总钱数，然后就能计算出另一个玩家能取出的钱数，二者比较就知道第一个玩家能否赢了

正序情况下，应当初始化dp[0...3]，求解dp[i]，此时需要dp[i+n]，所以做不了。
https://segmentfault.com/a/1190000004455242

定义dp[i]表示从i到end能取到的最大值

当我们在i处，有两种选择：

1.若取values[i]，对方可以取values[i+1] 或者values[i+1] + values[i+2]

当对方取values[i+1] 后，我们只能从 i+2 到end内取，我们所取得最大值是dp[i+2], 注意：对方所选取的结果一定是使得我们以后选取的值最小

当对方取values[i+1] + values[i+2]后，我们只能从i+3到end内取，我们所取得最大值是dp[i+3]。

此时：dp[i] = values[i] + min(dp[i+2],dp[i+3]) , 注意：对方所选取的结果一定是使得我们以后选取的值最小

2.若取values[i] + values[i+1],对方可取values[i+2] 或者values[i+2] + values[i+3]

当对方取values[i+2]后，我们只能从i+3到end内取，我们取得最大值是dp[i+3]

当对方取values[i+2]+values[i+3]后，我们只能从i+4到end内去，我们取得最大值是dp[i+4]

此时：dp[i] = values[i] + values[i+1]+min(dp[i+3],dp[i+4])

这里的取最小值和上面一样的意思，对方选取过之后的值一定是使得我们选取的值最小，对方不傻并且还很聪明

最后我们可以取上面两个dp[i]的最大值，就是答案，这里意思是：对方留得差的方案中，我们选取的最大值。

    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];
    }

http://shaowei-su.github.io/2015/12/18/lintcode4/
1st: We take only one coins which has values[i], then the other player will give us a choices between min(dp[i+2], dp[i+3]), ( she takes one or two coins).

2nd: Same as above analyze, we take two coins, then the max value we will get is values[i] + values[i+1] + min(dp[i+3],dp[i+4]). Finally, if dp[0] > sum - dp[0] we can win or we lose.(sum is the total value of the coins, dp[0] means the maximum possible value we can get from first coin to the last one).

    public boolean firstWillWin(int[] values) {
        // write your code here
        if (values == null || values.length == 0) {
            return false;
        }
        if (values.length <= 2) {
            return true;
        }
        int n = values.length;
        int[] dp = new int[n + 1];
        dp[n] = 0;
        dp[n - 1] = values[n - 1];
        dp[n - 2] = values[n - 2] + values[n - 1];
        dp[n - 3] = values[n - 3] + values[n - 2];

        for (int i = n - 4; i >= 0; i--) {
            dp[i] = values[i] + Math.min(dp[i + 1 + 1], dp[i + 1 + 2]);
            dp[i] = Math.max(dp[i], values[i] + values[i + 1] + Math.min(dp[i + 2 + 1], dp[i + 2 + 2]));
        }
        int sum = 0;
        for (int a: values) {
            sum += a;
        }
        return dp[0] > sum - dp[0];

    }

X. 方法二 - stores diff
https://www.jiuzhang.com/solutions/coins-in-a-line-ii/

public boolean firstWillWin(int[] A) {

int n = A.length;

int[] f = new int[n + 1];

f[n] = 0;

int i;

for (i = n - 1; i >= 0; --i) {

f[i] = A[i] - f[i + 1];

if (i < n - 1) {

f[i] = Math.max(f[i], A[i] + A[i + 1] - f[i + 2]);

}

return f[0] >= 0;

}

public boolean firstWillWin(int[] values) {

int n = values.length;

int[] sum = new int[n + 1];

for (int i = 1; i <= n; ++i)

sum[i] = sum[i - 1] + values[n - i];

int[] dp = new int[n + 1];

dp[1] = values[n - 1];

for (int i = 2; i <= n; ++i)

dp[i] = Math.max(sum[i] - dp[i - 1], sum[i] - dp[i - 2]);

return dp[n] > sum[n] / 2;

}

http://techinpad.bogspot.com/2015/05/lintcode-coins-in-line-ii.html
For any index i, we can know the gap between the two players if the first player moves from it. Suppose the first player moves from i and it wins f[i](the gap). If the second player moves from it, we should consider f[i] as a loss of the first player.

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

方法三 http://www.meetqun.com/thread-9798-1-1.html
第二题，每次可以从左边拿一个或两个，要点就在于每个人都是取获益最大的，所以要用max{min{}}

public static boolean firstWillWin(int[] A) {
// write your code here8 t; D6 B$ Q, u% _0 m- S
if(A.length <= 2) return true;
int[] D = new int[A.length+1];
D[A.length] = 0; H, [- j. B0 n
D[A.length-1] = A[A.length-1];
D[A.length-2] = A[A.length-2] + A[A.length-1];
D[A.length-3] = A[A.length-3] + A[A.length-2];
for(int i=A.length-4; i>=0; i--) {$ N p/ `) I" l
D【i】 = A【i】 + Math.min(D[i+1+1], D[i+1+2]);
D【i】 = Math.max(D【i】, A【i】+A[i+1]+Math.min(D[i+2+1], D[i+2+2]));: S) T2 S! R) Q! n2 L
}
int sum = 0;# ]9 T8 T% \4 p/ v# H
for(int a : A) sum += a;
return D[0] > sum-D[0];
}

https://codesolutiony.wordpress.com/2015/05/24/lintcode-coins-in-a-line-ii/

    public boolean firstWillWin(int[] values) {

        if (values == null || values.length <= 2) {

            return true;

}

        int second = values[values.length - 1];

        int first = values[values.length - 2] + second;

        int sum = first;

        for (int i = values.length - 3; i >= 0; i--) {

            sum += values[i];

            int cur = sum - Math.min(second, first);

            second = first;

            first = cur;

}

        return first > (sum - first);

}

http://blog.csdn.net/haifischxia/article/details/52250611
https://zhengyang2015.gitbooks.io/lintcode/content/coins_in_a_line_ii_395.html

http://www.jiuzhang.com/solutions/coins-in-a-line-ii/

    public boolean firstWillWin(int[] values) {
        // write your code here
        int n = values.length;
        int []dp = new int[n + 1];
        boolean []flag =new boolean[n + 1];
        int []sum = new int[n+1];
        int allsum = values[n-1];
        sum[n-1] = values[n-1];
        for(int i = n-2; i >= 0; i--) { 
            sum[i] += sum[i+1] + values[i];
            allsum += values[i];
        }
        return allsum/2 < MemorySearch(0, n, dp, flag, values, sum);
    }
    int MemorySearch(int i, int n, int []dp, boolean []flag, int []values, int []sum) {
        if(flag[i] == true)
            return dp[i];
        flag[i] = true;
        if(i == n)  {
            dp[n] = 0;  
        } else if(i == n-1) {
            dp[i] = values[i];
        } else if(i == n-2) {
            dp[i] = values[i] + values[i + 1]; 
        } else {
            dp[i] = sum[i] -
                Math.min(MemorySearch(i+1, n, dp, flag, values, sum) , MemorySearch(i+2, n, dp, flag, values, sum));
        }
        return dp[i];
    }
    public boolean firstWillWin(int[] values) {
        // write your code here
        int []dp = new int[values.length + 1];
        boolean []flag =new boolean[values.length + 1];
        int sum = 0;
        for(int now : values) 
            sum += now;
        
        return sum < 2*MemorySearch(values.length, dp, flag, values);
    }
    int MemorySearch(int n, int []dp, boolean []flag, int []values) { 
        if(flag[n] == true)
            return dp[n];
        flag[n] = true;
        if(n == 0)  {
            dp[n] = 0;  
        } else if(n == 1) {
            dp[n] = values[values.length-1];
        } else if(n == 2) {
            dp[n] = values[values.length-1] + values[values.length-2]; 
        } else if(n == 3){
            dp[n] = values[values.length-2] + values[values.length-3]; 
        } else {
            dp[n] = Math.max(
                Math.min(MemorySearch(n-2, dp, flag,values) , MemorySearch(n-3, dp, flag, values)) + values[values.length-n],
                Math.min(MemorySearch(n-3, dp, flag, values), MemorySearch(n-4, dp, flag, values)) + values[values.length-n] + values[values.length - n + 1]
                );
        }
    
        return dp[n];
    }

最近看到谷歌面经有问，每次可以拿1-3个纸牌的情况，不同的是纸牌能有负分。

拿纸牌游戏，纸牌上面有值，比如说 100， 1， -1， 2， 200， 1. 然后两个人轮流拿，直到拿完。但是每次只能拿从左边数起的前三个，但是如果你要拿第三个，就必须前两个都拿了，你要拿第二个，就必须第一个也拿了，大家都最优策略，问最后第一个人能拿多少分。

LintCode 395 - Coins in a Line II

Labels

Popular Posts