# Let me try to explain the DP solution

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

• @readonlyfile good try, but not clear enough.

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