6/24, 博弈类 DP

Coins in a Line

这题当然有取巧的 % 3 做法，不过不是很适合 generalize 到其他问题上。

Optimal Substructure

• 全局解 win(n) 取决于 win(n - 1) 和 win(n - 2) 的解，可以由 subproblem 的解构造出全局解。

Overlap Subproblem

• 就像 Fibonacci Number 结构一样。

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
        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++){
            dp[i] = (!dp[i - 1]) || (!dp[i - 2]);
        }

        return dp[n];
    }
}

Coins in a Line II

当存在“价值”之后，这题就是比较典型的博弈问题了，在 AI 里最常用的是 MiniMax 算法，如图所示，对于当前玩家来讲，会在当前的选择中选择 Max Profit; 而下一层对手的回合对手会选择留下 Min Profit 的走法。

按照 MiniMax 算法的思路，游戏策略如下：

当前还有 n 个硬币时 F(n)，每一步都可以选择拿 1 或 2 个硬币；

• 自己拿 1 个，对手子问题F(n - 1)：

  • 对手拿 1 个 - 自己下一步为F(n - 2)；

  • 对手拿 2 个 - 自己下一步为F(n - 3);

• 自己拿 2 个，对手子问题F(n - 2)：

  • 对手拿 1 个 - 自己下一步为F(n - 3)；

  • 对手拿 2 个 - 自己下一步为F(n - 4);

其中因为隔了一步对手的回合，自己的下一个 subproblem 值一定为两种可能中最小的一个。而对于本回合，自己要取拿 1 或 2 个硬币中受益最大的选择。

一次处理一个回合的 MiniMax 过程。

public class Solution {
    /**
     * @param values: an array 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(n <= 2) return true;

        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        dp[1] = values[n - 1];
        dp[2] = values[n - 1] + values[n - 2];

        int sum = 0;
        for(int num : values){
            sum += num;
        }

        return 2 * memoizedSearch(n, values, dp) > sum;
    }

    private int memoizedSearch(int coins, int[] values, int[] dp){
        if(coins < 0) return 0;
        if(dp[coins] != -1) return dp[coins];
        int n = values.length;

        int oneMax = values[n - coins] + Math.min(memoizedSearch(coins - 2, values, dp), 
                                                  memoizedSearch(coins - 3, values, dp));

        int twoMax = values[n - coins] + values[n - coins + 1] 
                     + Math.min(memoizedSearch(coins - 3, values, dp), 
                                memoizedSearch(coins - 4, values, dp));

        dp[coins] = Math.max(oneMax, twoMax);
        return dp[coins];
    }
}

Coins in a Line III

深入理解了上一道题之后，这题就变得非常好做了。相比上一道题，这个问题在决策分支上做了变化，一次只能拿一个硬币，但是有两个位置选择。换句话说，每一步依然会有两个分支，但是结构略有不同。

这种结构上的不同影响最大的是 dp[][]，因为我们不能再固定一端，用一个维度来表示剩下硬币构成的数组，因为从两端取硬币的时候，总共的区间数量 (start, end) 是 O(n^2)，需要用两个维度表示。

• dp[start][end] 当前玩家从index = (start, end) 区间内的最大 value

除此之外题目的结构和记忆化搜索并没有太大区别，依然是 MiniMax + Memoization.

ps: 假设没有面值为 0 的硬币，相比上一题跳过了 Arrays.fill -1 的初始化。

public class Solution {
    /**
     * @param values: an array 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(n <= 1) return true;

        // dp[i][j] = maximum value current player can get
        // between start = i, end = j
        int[][] dp = new int[n][n];

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

        int sum = 0;
        for(int num : values){
            sum += num;
        }

        return 2 * memoizedSearch(0, n - 1, values, dp) > sum;
    }

    private int memoizedSearch(int start, int end, int[] values, int[][] dp){
        if(start > end) return 0;
        if(dp[start][end] != 0) return dp[start][end];

        int takeLeft = values[start] 
                    + Math.min(memoizedSearch(start + 2, end, values, dp),
                               memoizedSearch(start + 1, end - 1, values, dp));

        int takeRight = values[end] 
                    + Math.min(memoizedSearch(start + 1, end - 1, values, dp),
                               memoizedSearch(start, end - 2, values, dp)); 

        dp[start][end] = Math.max(takeLeft, takeRight);
        return dp[start][end];
    } 
}

Guess Number Higher or Lower II

这题按类型分的话可以划为博弈类 DP，类似的还有 Lintcode 上的 Coins in a Line 1,2,3

我们先定义 dp[j]，代表着如果我们在区间 [i , j] 内进行查找，所需要的最少 cost 来保证找到结果。(当然，因为给定数字是 [1, n]，这里有一个 index off by one 的问题)。不难发现对于最开始的函数输入 n ，我们的最终结果就是 dp[0][n - 1] ，也即数字区间 [1 , n] 保证得到结果所需要的最小 cost.

如果以 top-down recursion 的方式分析这个问题，可以发现对于区间 [i, j] ，我们的猜测 i <= k <= j 我们可能出现以下三种结果： 1. k 就是答案，此时子问题的额外 cost = 0 ，当前位置总 cost = k + 0; 2. k 过大，此时我们的有效区间缩小为 [i , k - 1] 当前操作总 cost = k + dp[k - 1]; 3. k 过小，此时我们的有效区间缩小为 [k + 1 , j] 当前操作总 cost = k + dp[k + 1][j];

由于我们需要 “保证得到结果”，也就是说对于指定 k 的选择，我们需要准备最坏情况 cost 是以下三种结果生成的 subproblem 中cost 最大的那个； 然而同时对于一个指定区间 [i , j] ，我们可以选择任意 i <= k <= j ，对于这个 k 的主观选择可以由我们自行决定，我们要选的是 k s.t. 其子问题的 cost + 当前操作 cost 最小的一个，至此，每次决策就构成了一次 MiniMax 的博弈。

同时因为我们有很多的 overlapping subproblems ，而且问题本身具有 optimal substructure，提高算法效率最简单直观的方式，就是用 int[][] dp 做缓存，来进行自顶向下的记忆化搜索 ( top-down memoized search).

public class Solution {
    public int getMoneyAmount(int n) {
        // dp[i][j] min cost to guarantee to win from interval [i , j]
        return getMinCost(0, n - 1, new int[n][n]);
    }

    private int getMinCost(int start, int end, int[][] dp){
        if(start >= end) return 0;

        if(dp[start][end] != 0) return dp[start][end];

        int minCost = Integer.MAX_VALUE;
        for(int i = start; i < end; i++){
            minCost = Math.min(minCost,  (i + 1) + Math.max(getMinCost(start, i - 1, dp), 
                                                            getMinCost(i + 1, end, dp)));
        }
        dp[start][end] = minCost;

        return dp[start][end];
    }
}