Guess number higher or lower ii

Math Dynamic Programming Game Theory

52.5% acceptance

Jan 12, 2026

2329

2165

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

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 len in 2..=n {
      for i in 1..=n - len + 1 {
        let j = i + len - 1;
        dp[i][j] = i32::MAX;
        
        for k in i..j {
          let cost = k as i32 + dp[i][k - 1].max(dp[k + 1][j]);
          dp[i][j] = dp[i][j].min(cost);
        }
      }
    }
    
    dp[1][n]
  }
}