[Leetcode]375. Guess Number Higher or Lower II

https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

上一道题 GuessNumber 的升级版。然鹅，并看不懂题目。。。一开始想的是用二分法继续，求值，就像一道数学题，写完测试，不对。。。然后就很蒙圈，看提示，说要用dp，说要用mixmax，不知道啥是minmax的小白我看了半天才看懂那个维基百科链接。看完之后，呵呵，还是不懂。于是就只能搜索答案了。。。

这篇文章老外给的例子不错，举个栗子，哈哈。但是栗子之后就没有啥我能看懂的解释。但是有一个作者说了这句话，把dp的地推公式给解释了，很容易看懂。在1-n个数里面，我们任意猜一个数(设为i)，保证获胜所花的钱应该为 i + max(w(1 ,i-1), w(i+1 ,n))，这里w(x,y))表示猜范围在(x,y)的数保证能赢应花的钱，则我们依次遍历 1-n作为猜的数，求出其中的最小值即为答案，即最小的最大值问题
一亩三分地这个不错，讲的还算清楚，就是有个地方打错了应该是i打成了start。下面这个是leetcode的讨论区解释https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation
For each number x in range[i~j]
we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
--> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.
then we get DP([i~j]) = min{xi, ... ,xj}
--> // this min makes sure that you are minimizing your cost.递推公式还挺简单的其实，就是不好想。

我们先定义 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[i][k - 1];
3. k 过小，此时我们的有效区间缩小为 [k + 1 , j] 当前操作总 cost = k + dp[k + 1][j];
分析到这里，dp很明显，因为我们要不断变换i,j区间，而这个区间的数值可能是某一步算好的，这样我们就不用再算一遍了。

有纯的iteration的，比如这个，https://discuss.leetcode.com/topic/51358/java-dp-solution。

这个理解了之后编程还是不会，而且是iteration和recursion的全面不会。
recursion需要有终止条件，这道题的终止条件是啥呢？个人觉得，要是写不出来code，就是题目还没理解透彻，懂理解明白了，自然也有能写出来了。终止条件第一个是基本上所有recursion都有的就是start 大于等于end，这里说明我们找到最后一个数，得到答案，所以与要钱，就是0. 第二个终止条件我没想出来，这也就是导致我提交的时候最后超时了。它是，如果找到我们以前算过的数，dp对应的数值，应该返回直接。我已开始没加这个，超时了，英文即使算过也会再算一遍，这个是指数增加的，同时失去了我们dp的全部含义以前的都白算了，所以，这个终止条件不要忘了。

还有一个坑就是边界的坑，钱是从1开始算的，但是我们数组是0开始的。最开始我就是初始化数组长度为n，但是计算的时候要不停的+1,导致后来很烦躁并且算不清楚不了，后来干脆把初始数组设置长一点，这样我们可以从1开始算。我为了代码好理解，所有数组初始化成max值。也可以用默认的0做初始化。

AC 答案 recursion：

public class Solution {
{
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+1][n+1];
        for(int i=0; i<n+1; i++){
            for(int j=0; j<n+1; j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        return helper(1, n, dp);
    }
    
    public int helper(int start, int end, int[][] dp){
        if(start >= end){
            return 0;
        }
        if(dp[start][end] != Integer.MAX_VALUE){
            return dp[start][end];
        }
        for(int i=start; i<end+1; i++){
            dp[start][end] = Math.min(dp[start][end], i+Math.max(helper(start, i-1, dp),helper(i+1,end, dp)));
        }
        return dp[start][end];
    }
}

再来看Iteration的解法。虽然我没看懂，但是先贴上来。。。

public class Solution {
    public int getMoneyAmount(int n) {
        if (n == 1) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int jminusi = 1; jminusi < n; jminusi++) {
            for (int i = 0; i + jminusi <= n; i++) {
                int j = i + jminusi;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.min(dp[i][j],
                                        k + Math.max(k - 1 >= i ? dp[i][k - 1] : 0,
                                                     j >= k + 1 ? dp[k + 1][j] : 0));
                }
            }
        }
        return dp[1][n];
    }
}

开始的时候，总也搞不清楚这道题和第一题有什么区别。甚至用二分法来求解，当然结果是错的。后来终于想明白了，通俗的讲，第一题二分法是让我们查找到次数最少，而这道题是让我们找到钱最少的，也就是查找的和最小。每一次找的位置正中间，不一定是最好的。比如1，2，3，4这四个数，如果二分法，答案是5.但是我们可以让他变成4，先找1，然后3；或者先3，后1. 一开始拿到题有点慌，发下变化的量太多，首先选了那个数不知道，然后每一步先选啥不知道，感觉简直就是排列组合。先后选都有不同。但仔细分析之后发现不是的。我们不用关心具体被选中的数是哪个，只要让每一步都走错看看最后逼上梁山，最后一步走对的时候话费多少就行了。选一次就蒙对了不行，我们一定要每一步都走错，找到最后。