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

这个帖子总结的很好

public boolean firstWillWin(int[] values) {
        int n =values.length;
        if(n == 0) return false;
        if(n <= 2) return true;
        int[] dp = new int[n+1];
        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--){
            int min1 = values[i]+Math.min(dp[i+2], dp[i+3]);
            int min2 = values[i]+values[i+1]+Math.min(dp[i+3], dp[i+4]);
            dp[i] = Math.max(min1, min2);
        }
        int sum = 0;
        for(int num : values) sum+=num;
        return 2*dp[0]>sum;
    }

当存在“价值”之后，这题就是比较典型的博弈问题了，在 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 过程。

看到这里其实minmax就是一个top down的过程, 中间用memorization优化. 中间取值是通过"一大一小"或"一小一大"博弈来取.

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) {
        int[][] dp = new int[n][n];
        int cost = getMinCost(dp, 0, n-1);
        return cost;
    }

    public int getMinCost(int[][] dp, int start, int end){
        if(start>=end) return 0;
        if(dp[start][end]!=0) return dp[start][end];
        int cost = Integer.MAX_VALUE;
        for(int i=start;i<=end;i++){
            int submax =  (i+1)+ Math.max(getMinCost(dp, start, i-1), getMinCost(dp, i+1, end)); //gurantee to find
            cost = Math.min(cost, submax);//minimize the cost
        }
        dp[start][end] = cost;
        return cost;
    }
}

Predict the Winner

• 一次AC, 都是套路

• 首先确定是MaxMin, top-down approach, dp打表优化

• 对于player1 在range [start,end]区间取得的最大值

  • 如果player1取头元素start (option1)

    • 那么player 2会取start+1, 留给player1 [start+2, end]

    • player2取end, 留给player1 [start+1, end-1]

  • 如果player1取尾元素end (option2)

    • player2取start, 留给player1[start+1, end]

    • player2取end-1, 留给player1[start,end-2]

• player2 只会留给player1最少的分数

int option1 = nums[start] + Math.min(getMax(nums,dp,start+2,end), getMax(nums,dp, start+1, end-1));
int option2 = nums[end] + Math.min(getMax(nums, dp, start+1, end-1), getMax(nums,dp, start, end-2));

• player1 从选择中试图获取最大

• int maxscore = Math.max(option1, option2);
  

public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        if(nums.length<=1) return true;
        int[][] dp = new int[nums.length][nums.length];
        int score = getMax(nums, dp, 0, nums.length-1);
        int sum = 0;
        for(int num:nums) sum+=num;
        return score*2>=sum;
    }

    public int getMax(int[]nums, int[][] dp, int start, int end){
        if(start>end) return 0;
        if(start==end) return nums[start];
        if(dp[start][end]!=0) return dp[start][end];
        int option1 = nums[start] + Math.min(getMax(nums,dp,start+2,end), getMax(nums,dp, start+1, end-1));
        int option2 = nums[end] + Math.min(getMax(nums, dp, start+1, end-1), getMax(nums,dp, start, end-2));
        int maxscore = Math.max(option1, option2);
        dp[start][end] = maxscore;
        return maxscore;
    }
}