312. Guess Number Higher or Lower II
The guessing game now costs money. A secret number is chosen from 1 to n. Each time you guess a number x and you're wrong, you pay x dollars and are told whether the secret is higher or lower. A correct guess costs nothing, but running out of money before finding the secret means you lose.
Your function receives n and returns the smallest amount of money that guarantees you can find the secret — enough to survive even the unluckiest possible secret, assuming you play the best possible strategy.
Note this is not the binary-search question: guessing the midpoint minimizes the number of questions, but expensive high guesses can make it the wrong way to minimize cost.
Example 1:
Input: n = 10
Output: 16
Explanation: One guaranteed strategy: guess 7 (pay 7 if wrong). If the secret is higher, guess 9 (pay 9) — total 16 covers the worst case there. If lower, guess 3 then 5 (or 1), never exceeding 16 in any branch. No strategy can guarantee a win with 15.
Example 2:
Input: n = 2
Output: 1
Explanation: Guess 1. If it's right you pay nothing; if it's wrong you pay 1 and the secret can only be 2. Guessing 2 first would risk paying 2.
Constraints:
- 1 ≤ n ≤ 200
Hints:
For n = 1 the answer is 0, and for n = 2 it's 1 (guess the cheaper number first). Try n = 3 by hand: which first guess makes the worst case cheapest?
"Guarantee" means your budget must cover the worst answer to every guess. If you guess x in the range [lo, hi], the adversary sends you to whichever side costs more: x + max(cost(lo, x-1), cost(x+1, hi)).
That recurrence only ever mentions contiguous subranges [lo, hi] — there are O(n²) of them. Memoize, or fill a table from short ranges to long ones.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 10
Expected output: 16