# Leetcode 375 - Guess number higher or lower II

`Note:`

- To pick the
`BEST among the WORST`

. - Not a
`binary search`

question, so we need to find out every possible move. - DON’T define dfs as
`(low, high, sum)`

.- For example, when
`low == 1, high == 3`

and we pick`3`

, the next iteration is`dfs(1, 2, 3)`

. - What we will get is
`min(3 + 1, 3 + 2)`

. But apparently,`dfs = 1`

.

- For example, when

`Question:`

We are playing the Guessing Game. The game will work as follows:

- I pick a number between
`1`

and`n`

. - You guess a number.
- If you guess the right number, you win the game.
- If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
- Every time you guess a wrong number
`x`

, you will pay`x`

dollars. If you run out of money, you lose the game.

Given a particular `n`

, return the minimum amount of money you need to `guarantee a win regardless of what number I pick`

.

`Example:`

1 | Input: n = 10 |

`Code:`

`DP O(n^3)`

1 | /** |

`DFS memo`

1 | /** |