Skip to content

375. Guess Number Higher or Lower II

Approach 1: Top-down

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int getMoneyAmount(int n) {
    vector<vector<int>> mem(n + 1, vector<int>(n + 1, INT_MAX));
    return getMoneyAmount(1, n, mem);
  }

 private:
  // Returns the minimum money you need to guarantee a win of picking i..j.
  int getMoneyAmount(int i, int j, vector<vector<int>>& mem) {
    if (i >= j)
      return 0;
    if (mem[i][j] != INT_MAX)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = min(mem[i][j], max(getMoneyAmount(i, k - 1, mem),
                                     getMoneyAmount(k + 1, j, mem)) +
                                     k);

    return mem[i][j];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int getMoneyAmount(int n) {
    int[][] mem = new int[n + 1][n + 1];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    return getMoneyAmount(1, n, mem);
  }

  // Returns the minimum money you need to guarantee a win of picking i..j.
  private int getMoneyAmount(int i, int j, int[][] mem) {
    if (i >= j)
      return 0;
    if (mem[i][j] != Integer.MAX_VALUE)
      return mem[i][j];

    for (int k = i; k <= j; ++k)
      mem[i][j] = Math.min(mem[i][j], Math.max(getMoneyAmount(i, k - 1, mem), //
                                               getMoneyAmount(k + 1, j, mem)) +
                                          k);

    return mem[i][j];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def getMoneyAmount(self, n: int) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """Returns the minimum money you need to guarantee a win of picking i..j.
      """
      if i >= j:
        return 0
      return min(max(dp(i, k - 1), dp(k + 1, j)) + k
                 for k in range(i, j + 1))

    return dp(1, n)

Approach 2: Bottom-up

  • Time: $O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int getMoneyAmount(int n) {
    // dp[i][j] := the minimum money you need to guarantee a win of picking i..j
    vector<vector<int>> dp(n + 2, vector<int>(n + 2));

    for (int d = 1; d < n; ++d)
      for (int i = 1; i + d <= n; ++i) {
        const int j = i + d;
        dp[i][j] = INT_MAX;
        for (int k = i; k <= j; ++k)
          dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k);
      }

    return dp[1][n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int getMoneyAmount(int n) {
    // dp[i][j] := the minimum money you need to guarantee a win of picking i..j
    int[][] dp = new int[n + 2][n + 2];

    for (int d = 1; d < n; ++d)
      for (int i = 1; i + d <= n; ++i) {
        final int j = i + d;
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = i; k <= j; ++k)
          dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][k - 1], dp[k + 1][j]) + k);
      }

    return dp[1][n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def getMoneyAmount(self, n: int) -> int:
    # dp[i][j] := the minimum money you need to guarantee a win of picking i..j
    dp = [[0] * (n + 2) for _ in range(n + 2)]

    for d in range(1, n + 1):
      for i in range(1, n - d + 1):
        j = i + d
        dp[i][j] = math.inf
        for k in range(i, j + 1):
          dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k)

    return dp[1][n]