這題是九章的題目，有基本題跟另外兩個 follow up。

Coins in a line

Question

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?

Solution

利用記憶化搜索，從大到小。另外，只考慮先手的情況就行

    public boolean firstWillWin(int n) {
        int[] dp = new int[n + 1];
        return helper(dp, n);
    }

    public boolean helper(int[] dp, int n) {
        if (dp[n] == 1) {
            return true;
        } else if (dp[n] == 2) {
            return false;
        }

        if (n <= 0) {
            return false;
        } else if (n == 1) {
            return true;
        } else if (n == 2) {
            return true;
        } else {
            if ((helper(dp, n - 2) && helper(dp, n - 3)) || (helper(dp, n - 3) && helper(dp, n - 4))) {
                dp[n] = 1;
                return true;
            } else {
                dp[n] = 2;
            }
        }

        return false;
    }

也可以把轉移方程改為： dp[i] = !dp[i - 1] || !dp[i - 2];

Coins in a line II

Question

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?

Solution

這個 follow up 題，如果用 boolean[] dp，就會掉入題目的陷阱。因此還是得用原本的 int[] dp，只是最後在判斷的時候，透過 dp[n] 是否大於 sum / 2 來決定對或錯。至於當 n = 3 時，為什麼 dp[n] = values[values.length - 2] + values[values.length - 3]？原因是我們定義 dp[n] 為當有 n 個硬幣時，先手所能取得的最大價值。因此當 n = 3 時，例如 [1,2,2]，先手先取，不管如何，最大價值絕對是第一個跟第二個都取

    public boolean firstWillWin(int[] values) {
        int len = values.length, sum = 0;
        for (int i = 0; i < len; i++) {
            sum += values[i];
        }
        int[] dp = new int[len + 1]; // dp[i] 代表在 i 個硬幣，先手取硬幣的價值
        return sum < 2 * helper(len, dp, values);
    }

    public int helper(int n, int[] dp, int[] values) {
        if (dp[n] != 0) {
            return dp[n];
        }

        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(helper(n - 2, dp, values), helper(n - 3, dp, values)) + values[values.length - n], Math.min(helper(n - 3, dp, values), helper(n - 4, dp, values)) + values[values.length - n] + values[values.length - n + 1]
                );
        }
        return dp[n];
    }

Coins in a line III

Question

There are n coins with different value in a line. Two players take turns to take one coin from the end of one 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?

Solution

Coins in a line 的終極問題。如果給的 array 是 [1,2,2]，從三個硬幣降到兩個硬幣時，有可能是 [1,2] 或者 [2,2]，因此原本的一維 dp 不夠用，要拓展到二維。

因此，dp[x][y] 代表還剩從 x 到 y 的硬幣，現在先手所取的最大價值。轉移方程為：

dp[x][y] = Math.max(Math.min(dp[x + 2][y], dp[x + 1][y - 1]) + a[x], Math.min(dp[x][y - 2], dp[x + 1][y - 1]) + a[y]);