375. Guess Number Higher or Lower II

Description of Problem

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
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
    - If this is my number, your total is $0. Otherwise, you pay $7.
    - If my number is higher, the range is [8,10]. Guess 9.
        - If this is my number, your total is $7. Otherwise, you pay $9.
        - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
        - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
    - If my number is lower, the range is [1,6]. Guess 3.
        - If this is my number, your total is $7. Otherwise, you pay $3.
        - If my number is higher, the range is [4,6]. Guess 5.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
            - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
            - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
        - If my number is lower, the range is [1,2]. Guess 1.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
            - If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

Example 2:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

Example 3:

Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is $0. Otherwise, you pay $1.
    - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

Constraints:

1 <= n <= 200

Solution

Tags: Dynamic Programming,Game Theory

Explanation

Denote \( S_{i,j} \) as a solution of a sub-problem which is the minimum of amount of money to guarentee the successful guess while the range is i to j (inclusively). Suppose we pick k, the amount to guarentee the successful guess is \( k+ \max(S_{i,k-1}, S_{k+1,j}) \). Hence, we get the recursive formula. \[ S_{i,j} = \begin{cases} 0 & \text{if } i \ge j \\ \min_{k \in \lbrace i,i+1,...,j \rbrace} \lbrace k + \max(S_{i,k-1}, S_{k+1,j}) \rbrace & \text{if } i \lt j \end{cases} \]

We observe that the Solution of \(S_{i,j}\) depends on either the solutions on the left or the bottom in the dp table. Thus, the algorithm loops over the dp table diagonally (It makes the below code hard to read.).

Exmaple of diagonal loop

Suppose it is 5x5 dp table:
1 2 3 4 5 
  1 2 3 4
    1 2 3
      1 2
        1

Number i represents the i-th inner loop

Code (Rust)

impl Solution {
    pub fn get_money_amount(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![ vec![0 ; n + 1] ; n + 1];

        for i in 1..n {
            for j in 0..(n-i){
                let mut min = i32::MAX;
                let row = 1 + j;
                let col = 1 + j + i;

                for k in row..=col {
                    let a = if row >= 0  && row <= n && k >= 1 && k <= n + 1 { dp[row][k - 1] } else { 0 };
                    let b = if col >= 0 && col <= n && k + 1 >= 0 && k + 1 <= n {dp[k+1][col] } else { 0 };
                    min = min.min( k as i32 + a.max(b) );
                }

                dp[row][col] = min;
            }
        }

        return dp[1][n];
    }
}

Complexity

Time Complexity

\(T(n) = Theta(n^2)\)

Auxiliary Space

\(S(n) = Theta(n^2)\)