[LeetCode] Guess Number Higher or Lower II 猜数字大小之二

robotics-algorithm

---

参考文章链接

1 我的解决思路和问题描述

一个数字为$n$，在$n$中任意选一个数字作为$answer$，可以一直猜测下去，直到猜对。如果用 $x\in[1, n]$表示该次使用的猜测数字，如果猜错，则猜错的代价$cost(x) = x$。

所以对于 $n$ 中的其中一个 $answer$ ，我们如果要猜对的话，那么可能需要猜测很多次，假设我们采用的某种猜测策略需要猜测$m$次,每次猜的数字为$x_i$。那么为了猜对这个$answer$，我们的$m$次猜测错误代价总和表示为

$$answer:\sum\limits_{i=1}^m cost(x_i)=answer:\sum\limits_{i=1}^m x_i$$

考虑一般情况，在区间$[j, i], 1<=j<i<=n$中，如果我们使用类似分治法的思想，在区间中任取$k$作为猜测值，那么这个区间内的某一个$answer$的代价包括三个部分，$k$，$k$的左区间和$k$的右区间的代价和，表示为

$$answer: cost(k)+max(cost(k_{left}), cost(k_{right}))$$

也就是针对每一次猜测分割用一个局部最大值(local_max)加上$k$表示能够覆盖本次猜测的所有可能消耗的代价。

但是区间$[j,i]$中包括了$i-j$种 $k$ 的可能，所以我们需要遍历这$i-j$种可能，分别求出对应的代价，表示为

$$cost_j,...,cost_i$$

要注意，在区间$[j, i]$上计算代价时有两种可能，第一次取$k$作为猜测的分割点

• 如果$i-j=1$,那么直接求出区间代价为$j$,
• 如果$i-j>=2$,那么从$k = j+1到 k <= i-1$遍历，然后在所有的代价中取一个最小值，表示为$\min \space \{cost_j,...,cost_i\}$, 也称为全局最小值(global_min), 即为此区间代价。

现在还需要解决最后一个问题，如何保证我们前面的$cost(k_{left}), cost(k_{right})$是知道的？

需要两点保证
(1)总区间$[1, n]$,采用如下的遍历方式，

    for (int i = 2; i <= n; ++i)
    {
        for (int j = i-1; j >=1 ; --j)
        {
        }
    }

(2) 相差为1的区间代价计算方式
前面提到的，如果$i-j=1$,那么直接求出区间代价为$j$。
如上两点保证后面用到的每一个区间代价，都是经过前面计算的，也即是动态规划思想，利用前面计算的结果来计算当下的问题。

根据理解修改的网上的demo如下：

#include <iostream>
#include <climits>
#include <vector>
using namespace std;
//采用动态规划的思想
int GuessNumWithMinCost(int n)
{
    vector<vector<int>> min_cost(n+1,vector<int>(n+1,0));//方便从1开始访问下标
    // 1 ... j ... i ... n
    for (int i = 2; i <= n; ++i)
    {
        for (int j = i-1; j >=1 ; --j)// 先求[j,i]区间内的cost
        {
            int global_min = INT_MAX;//global_min使用一个较大的数初始化(eg: INT_MAX)
            for (int k = j+1; k <= i-1; ++k)////遍历区间[j,i], j+1<=k<=i-1,此处情况为i-j>=2
            {
                int local_max = k + max(min_cost[j][k-1], min_cost[k+1][i]);//local_max就是考虑局部最坏情况
                global_min = min(global_min, local_max);//global_min 就是考虑所有最坏情况后找出损失最小的情况
            }
            if(i-j>=2)
                min_cost[j][i] = global_min;
            else//i-j=1时
                min_cost[j][i] = j;
        }
    }
    // print min_cost matrix
    cout<<"min cost matrix is: \n";
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <i ; ++j)
        {
            cout<<min_cost[j][i]<<" ";  
        }
        cout<<endl;
    }
    return min_cost[1][n];
}
int main(int argc, char const *argv[])
{
    int n;
    cout<<"please input n: ";
    cin>>n;
    cout<<"The Min Cost("<<n<<") is: "<<GuessNumWithMinCost(n)<<endl;
    return 0;
}

2 网络解题思路

我们想，如果只有一个数字，那么我们不用猜，cost为0。如果有两个数字，比如1和2，我们猜1，即使不对，我们cost也比猜2要低。如果有三个数字1，2，3，那么我们就先猜2，根据对方的反馈，就可以确定正确的数字，所以我们的cost最低为2。如果有四个数字1，2，3，4，那么情况就有点复杂了，那么我们的策略是用k来遍历所有的数字，然后再根据k分成的左右两个区间，取其中的较大cost加上k。

当k为1时，左区间为空，所以cost为0，而右区间2，3，4，根据之前的分析应该取3，所以整个cost就是1+3=4。
当k为2时，左区间为1，cost为0，右区间为3，4，cost为3，整个cost就是2+3=5。
当k为3时，左区间为1，2，cost为1，右区间为4，cost为0，整个cost就是3+1=4。
当k为4时，左区间1，2，3，cost为2，右区间为空，cost为0，整个cost就是4+2=6。
综上k的所有情况，此时我们应该取整体cost最小的，即4，为最后的答案，这就是极小化极大算法。

有两个策略

• minimize the maximum loss you could possibly face
• minimize the expected loss

考虑第一个。