Coins in a line I

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.

思路：

做完三个题之后，个人倾向定义转移公式为 还剩i个硬币, 当前拿硬币的人最终是否获胜

dp[i] = true If dp[i-1] == false or dp[i-2] == false

如何理解这个公式在这里有点巧妙，当计算dp[i]的时候，你假设这次你会拿1个coin 或者你这次拿2个coins， 对手面对i-1或者i-2个硬币，只要任意一种情况dp是false最终他赢不了，你肯定就会根据那种情况去拿，最后你必胜。

public boolean firstWillWin(int n) {
        // write your code here
        if (n == 0)
            return false;

        if (n <= 2)
            return true;

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

        dp[0] = false;
        dp[1] = true;
        dp[2] = true;

        for (int i = 3; i <= n; i++) {
            if (dp[i-1] == false || dp[i-2] == false)
                dp[i] = true;
        }

        return dp[n];

    }

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?

思路：

注意题目要求从左向右拿，我们定义dp[i]是还剩i个硬币，当前取硬币的人最后最多取多少硬币

dp[i] = Max{sum[i] - dp[i-1], sum[i] - dp[i-2]}

可以理解为在还剩i个硬币的时候，所有硬币和为sum[i],如果当前去硬币的人取一个，那对手面对i-1个硬币最后取到最大值是dp[i-1],同理当前去硬币的人取2个，对手面对i-2个硬币最后取到最大值是dp[i-2]，当然现在取的人想要对手取到的最少， 所以就要取sum[i] -这两种情况的最小值。

在实现的过程中，因为从左向右取，所以计算还剩的sum时需要从数组的最后开始取，dp初始值也是要算最后的。

所以我更倾向于solution2，先把数组倒过来然后从左向右取。

Solution 1:

public boolean firstWillWin(int[] values) {
        // write your code here
        int n = values.length;

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

        // sum of rest coins value ** pick from left eg. sum[1] = values[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]);// sum[i] - Math.min(dp[i-1],dp[i-2])
        }

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


    }

Solution 2:

public boolean firstWillWin(int[] values) {
        // write your code here
        int n = values.length;

        for (int i = 0; i < values.length / 2; i++) {
            int temp = values[i];
            values[i] = values[values.length - 1 - i];
            values[values.length - 1 - i] = temp;
        }       


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

        // sum of rest coins value ** pick from left eg. sum[1] = values[n-1]
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i-1] + values[i-1];
        }

        int[] dp = new int[n+1];
        dp[1] = values[0];
        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;
    }

Coins in a line III

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[i][j] 从第i到第j的硬币，现在当前取硬币的人最后最多取硬币价值

sum[i][j] 从第i个到第j个硬币所以价值和

dp[i][j] = max{sum[i][j] - dp[i+1][j], sum[i][j] - dp[i][j-1]};

实现技巧：

sum[i][j] = sum[j] - sum[i-1]

实现的时候无法查看dp[i][j-1], 所以利用长度遍历

初始化sum和dp长度都用n+1

public boolean firstWillWin(int[] values) {
        // write your code here

        int n = values.length;
        int[] sum = new int[n + 1];

        // calc sum
        for (int i = 1; i <= n; ++i) 
            sum[i] = sum[i - 1] + values[i - 1];

       // from i to i calc dp
        int[][] dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++)
            dp[i][i] = values[i-1];

        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n; i++) {
                int j = i + len - 1;
                if (j > n)
                    continue;
                // sum of i to j
                int s = sum[j] - sum[i-1];
                //pick i or pick j
                dp[i][j] = Math.max(s - dp[i + 1][j], s - dp[i][j - 1]);
            }
        }

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