Let me try to explain the DP solution


  • 5
    R

    In fact , I have no idea why we should do like this . After looking some topic , I find only DP formula was given . So I am trying to explain it totally . It may be not right , but I'll try .

    First , for Chinese , just look this Chinese Thinking Progress. following is the English , and more concise.

    1. MinMax for Game

    you should think you are playing game : I and you . For one turn, I'll go first , and after I did action , you'll make a response , and give me hurt . Imaging I have N possible choices , if I choose the k-th choice , you know , I respected you, so I think you'll give me the biggest hurt as posisblility . Assuming you have T responses for my current action, I'll use max( T-Responses-Hurt-Value) as the harm of taking current action. After thinking this, if I am not stupid , and I am not radical, I'll choice the action which your max(T-Responses-Hurt-Value) is minimum, that is min_{k} { max{T-Response-hurt-value} }

    So , this the why Min Max.

    2. How to Suit with this Problem

    we ues R[i][j] to represents the minMax cost when guessing number in range [ i , j] .

    - Dynamic progress

    for range [i, j] , we have j-i+1 possible choices , for choice k ( i <= k <= j , and j > i ),

    1. Firstly we'll get your 3 possible responses , which is

      1. guess smaller , cost is R[k+1][j]

      2. guess bigger, cost is R[i][k-1]

      3. guess right , cost is 0

      you will give the biggest harm , that means , the final cost for choice k is

      max(R[k+1][j], R[i][k-1], 0) => max(R[k+1][j], R[i][k-1]) , because as smart as you , you can't let me guess right.

    2. So we get cost k ( as question saying ) for guessing error.

    In conclusion, R[i][j] = min_{k} { max(R[k+1][j], R[i][k-1]) }, where i<= k <= j

    Aforementioned formula is what you may see in some solution .

    - And the Edge Condition

    for R[x][x] , no matter how you smart , only one number is available, so cost is 0.

    That;s all , hope this helps .


  • 1

    @readonlyfile good try, but not clear enough.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.