375. 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.

问题描述

我们正在玩一个猜数游戏,游戏规则如下:

我从 1 到 n 之间选择一个数字,你来猜我选了哪个数字。

每次你猜错了,我都会告诉你,我选的数字比你的大了或者小了。

然而,当你猜了数字 x 并且猜错了的时候,你需要支付金额为 x 的现金。直到你猜到我选的数字,你才算赢得了这个游戏。

示例:
n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5,我会告诉你,我的数字更大一些,然后你需要支付5块。
第二轮: 你猜是7,我告诉你,我的数字更大一些,你支付7块。
第三轮: 你猜是9,我告诉你,我的数字更小一些,你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。

给定一个 n ≥ 1,计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

问题分析

  刚开始看到这个题,感觉是个数学问题,可以直接计算得出。写了很久都不AC,于是又老实写算法了。从算法角度看,这个题就是很直白的暴力破解,中间用到了DP来减小运算复杂度,还包含了取最大值和最小值运算,所以不太好分类,但是思想还是能理明白。最重要的一步DP就是i+max( [1,…,i-1] , [i+1,…,n] )。这里的[1,…,i-1]表示猜对这个短序列最少花的钱。
  下面举例说明。

  • 当序列很短的时候,一眼就能看出来最少花多少钱。比如长度为2的短序列:

    1 2

    显然猜1可以花钱最少,猜对不花钱,错了花1块,所以最多需要1块钱。

    长度为3的短序列同理。比如:

    2 3 4

    显然猜3可以花最少的钱,猜对不花钱,错了花3块,然后下一次一定可以猜对。所以最多需要3块钱。
    对于这种短序列,我们很快可以得到答案,直接每个数试一试就能知道结果。具体这样试,

    • 如果先猜2,错了再猜3(知道3比4花钱少),那么5块钱可以保证一定猜对。
    • 如果先猜3,不管对错,肯定能得到正确答案,那么只需3块钱。
    • 如果先猜4,错了再猜2(知道2比3花钱少),那么需要6块钱。
    • 综上,选最好的猜法,最少只要3块钱即可。
      这其实是我们内心的真实逻辑,写成代码就简单了,如果序列是[ i , i+1 ]和[ i-1 , i , i+1 ]这样的,直接猜i就好了。
  • 对于中长序列,比如1到4的序列怎么处理呢,其实逻辑一样:

    1 2 3 4

    上面[ 2 , 3 , 4 ]的例子里,猜2不对,我们知道该猜3而不是4。但对于这种长一点的序列,第一次没猜对,我们也不容易看出第二次猜哪个数比较好。
    如果没有策略,纯暴力搜索把所有猜法都试一遍,复杂度是指数级的。于是我们可以在暴力搜索的基础上将任务分解成一个个小任务,即用DP的思路,创建一个二维表格,记住小任务的解,最终得到大任务的解。
    比如前面[ 2 , 3 , 4 ]的例子里思路也是一样的。猜2不对,我们知道猜3而不是4,就是因为我们心里默认知道[ 3 , 4 ]这个小任务只需要猜3就够了,即[ 3 , 4 ]这个小任务只需要3块钱而不是4块钱。
    这里也是同理:

    • 先猜1

      1 2 3 4

      那么剩下的[ 2 , 3 , 4 ]猜什么呢。上述已经知道这个序列猜3花费最少。那么最终花费是1+3=4

    • 先猜2

      1 2 3 4

      要是大了,左边剩一个数肯定是对的,那么花费是0。要是小了,右边的序列[ 3 , 4 ]花费3足矣。那么最少需要花的钱就是2+max(左边0,右边3)=5。
      这里有个取最大的操作,原因是为了把所有情况都考虑进去,这样无论是哪一种情况,钱都是够的

    • 先猜3

      1 2 3 4

      要是大了,左边的序列[ 1 , 2 ]花费1足矣。要是小了,右边只剩一个数,花费0。那么这种情况下最少需要3+max(左边1,右边0)=4

    • 先猜4

      1 2 3 4

      剩下的[ 1 , 2 , 3 ]花费2,最终花费4+2=6。

      那么最终至少要花的钱就是min(先猜1,先猜2,先猜3,先猜4)=min(4,5,4,6)=4 。
      这里有个取最小值的操作,就是在所有暴力破解的方法中,找花钱最少的那种方法,这样就能用最少的钱猜到正确数字
      另外可以看出,我们每次都把任务分解成左右两个小任务,只要知道了小任务的最优值,就能求得大任务的最优值了。

  • 再举一个长序列的例子说明任务分解,比如1到10:

    1 2 3 4 5 6 7 8 9 10

    做法和上述一样,最外面的大循环直接for i in range(1,11)从头试到尾,这样把任务分成了两个小任务,即[1,…,i-1]和[i+1,…,10],然后只要我们知道每个小任务的解,那么先猜i的这个大任务的解就是i+max([1,…,i-1],[i+1,…,10])。

    • 比如我们先猜了6

      1 2 3 4 5 6 7 8 9 10

      任务被分解成1到5和7到10两个小任务,如果我们已经用一个数组存储了这两个小任务的解,那么这个大任务的解直接就是6+max([1,…,5],[7,…,10])
      所有1到10都试过之后,再取最小值,得到的就是花费最少的钱数了。即min( 先猜1花的钱 , … , 先猜10花的钱 )。

  • 最后的问题是怎么构造二维数组存储小任务的解呢,也很简单。这里以1到6举例,太长表格不好画。

    1 2 3 4 5 6

    表格建立如下,记为T:

    1 2 3 4 5 6
    1
    2
    3
    4
    5
    6

    行代表任务序列的终点,列代表任务序列的起点(这里行列表示含义互换也一样,只是我自己写代码的时候这么写了懒得改了)。表格中的数代表猜对这个序列至少需要花多少钱。比如T[5][2]就表示从2到5,最少需要花多少钱可以猜对。我们的任务就是填满这个表的下半部分。填满之后,T[6][1]也就是我们要的解。那么我们从头到尾填一遍。
    注意:这里我直接从1开始计数便于解释说明,代码的计数是从0开始的。

    • 首先初始化表格为0

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 0 0 0 0 0 0
      3 0 0 0 0 0 0
      4 0 0 0 0 0 0
      5 0 0 0 0 0 0
      6 0 0 0 0 0 0
    • 任务终点为1的时候,此时序列为[ 1 ],不用花钱就能猜对,则有T[1][1]=0。
      终点为1填写完毕。此时T没变

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 0 0 0 0 0 0
      3 0 0 0 0 0 0
      4 0 0 0 0 0 0
      5 0 0 0 0 0 0
      6 0 0 0 0 0 0
    • 任务终点为2的时候,
      任务起点先设为2,此时序列为[ 2 ],不用花钱,则有T[2][2]=0。
      下一步任务起点设为1,此时序列为[ 1 , 2 ],花1即可,则有T[2][1]=1。
      终点为2填写完毕,此时T为

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 1 0 0 0 0 0
      3 0 0 0 0 0 0
      4 0 0 0 0 0 0
      5 0 0 0 0 0 0
      6 0 0 0 0 0 0
    • 任务终点为3的时候,
      任务起点先设为3,此时序列为[ 3 ],不用花钱,则有T[3][3]=0。
      任务起点设为2,此时序列为[ 2 , 3 ],花钱2,则有T[3][2]=2。
      任务起点设为1,此时序列为[ 1 , 2 ,3 ],三个的短序列直接可得花钱为中间那个数,也就是2,则有T[3][1]=2。
      终点为3填写完毕,此时T为

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 1 0 0 0 0 0
      3 2 2 0 0 0 0
      4 0 0 0 0 0 0
      5 0 0 0 0 0 0
      6 0 0 0 0 0 0
    • 任务终点为4的时候,
      任务起点设为4,此时序列为[ 4 ],不花钱,T[4][4]=0。
      任务起点设为3,此时序列为[ 3 , 4 ],花钱3,则有T[4][3]=3。
      任务起点设为2,此时序列为[ 2 , 3 , 4 ],花钱3,则有T[4][2]=3。
      任务起点设为1,此时序列为[ 1 , 2 , 3 , 4 ],长度超过3了,要用中长序列的方式去计算。也就是前面举例的方式,有T[4][1]=min(先猜1花的钱,…,先猜4花的钱)
      \[
      \begin{array}{l}
      =min(1+[2,3,4] \ , \ 2+max([1],[3,4]) \ , \ 3+max([1,2],[4] \ , \ 4+[1,2,3])) \\
      =min(1+T[4][2] \ , \ 2+max(T[1][1],T[4][3]) \ , \ 3+max(T[2][1],T[4][4]) \ , \ 4+T[3][1]) \\
      =min(1+3 \ , \ 2+3 \ , \ 3+1 \ , \ 4+2) \\
      =4
      \end{array}
      \]

      即T[4][1]=4。
      终点为4填写完毕,此时T为

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 1 0 0 0 0 0
      3 2 2 0 0 0 0
      4 4 3 3 0 0 0
      5 0 0 0 0 0 0
      6 0 0 0 0 0 0
    • 任务终点为5的时候,
      任务起点设为5,此时序列为[ 5 ],不花钱,T[5][5]=0。
      任务起点设为4,此时序列为[ 4 , 5],花钱4,则有T[5][4]=4。
      任务起点设为3,此时序列为[ 3 , 4 ,5 ],花钱4,则有T[5][3]=4。
      任务起点设为2,此时序列为[ 2 , 3 , 4 ,5],有
      \[
      \begin{array}{l}
      T[5][2] \\
      =min(2+T[5][3],3+max(T[2][2],T[5][4]),4+max(T[3][2],T[5][5])) \\
      =min(2+4,3+4,4+2) \\
      =6
      \end{array}
      \]

      任务起点设为1,此时序列为[ 1 , 2 , 3 , 4 , 5 ],有
      \[
      \begin{array}{l}
      T[5][1] \\
      =min(1+T[5][2],2+max(T[1][1],T[5][3]),3+max(T[2][1],T[5][4]),4+max(T[3][1],T[5][5]),5+T[4][1]) \\
      =min(1+6,2+4,3+4,4+2,5+4) \\
      =6
      \end{array}
      \]
    • 终点为5填写完毕,此时T为

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 1 0 0 0 0 0
      3 2 2 0 0 0 0
      4 4 3 3 0 0 0
      5 6 6 4 4 0 0
      6 0 0 0 0 0 0
    • 任务终点为6的时候,
      任务起点设为6,此时序列为[ 6 ],不花钱,T[6][6]=0。
      任务起点设为5,此时序列为[ 5 , 6 ],花钱5,则有T[6][5]=5。
      任务起点设为4,此时序列为[ 4 , 5 , 6 ],花钱5,则有T[6][4]=5。
      任务起点设为3,此时序列为[ 3 , 4 , 5 , 6 ],有
      \[
      \begin{array}{l}
      T[6][3] \\
      =min(3+T[6][4],4+max(T[3][3],T[6][5]),5+max(T[4][3],T[6][6]),6+T[5][3]) \\
      =min(3+5,4+5,5+3,6+4) \\
      =8
      \end{array}
      \]

      任务起点设为2,此时序列为[ 2 , 3 , 4 , 5 , 6 ],有
      \[
      \begin{array}{l}
      T[6][2] \\
      =min(2+T[6][3],3+max(T[2][2],T[6][4]),4+max(T[3][2],T[6][5]),5+max(T[4][2],T[6][6]),6+T[5][2]) \\
      =min(2+8,3+5,4+5,5+3,6+6) \\
      =8
      \end{array}
      \]

      任务起点设为1,此时序列为[ 1 , 2 , 3 , 4 , 5 , 6 ],有
      \[
      \begin{array}{l}
      T[6][1] \\
      =min(1+T[6][2],2+max(T[1][1],T[6][3]),3+max(T[2][1],T[6][4]),4+max(T[3][1],T[6][5]),5+max(T[4][1],T[6][6]),6+T[5][1]) \\
      =min(1+8,2+8,3+5,4+5,5+4,6+6) \\
      =8
      \end{array}
      \]

      终点为6填写完毕,此时整个表格填写完毕。
      有T为

      1 2 3 4 5 6
      1 0 0 0 0 0 0
      2 1 0 0 0 0 0
      3 2 2 0 0 0 0
      4 4 3 3 0 0 0
      5 6 6 4 4 0 0
      6 8 8 8 5 5 0
    • 到此,T[6][1]=8即为结果。再把上述思路转为代码就搞定了。

代码

class Solution:
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        L = [[0]*(n+1) for i in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,i)[::-1]:
                M = n*n
                if i-j<=2:
                    M = i-1
                else:
                    for k in range(j+1,i):
                        M = min(M,k+max(L[k-1][j],L[i][k+1]))
                L[i][j] = M
        return L[n][1]

测试结果

  • Runtime:692 ms
  • beats 69.5% of python3 submissions

版权声明:本文为initial-h原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/initial-h/p/9536480.html