Leetcode

Guess Number Higher or Lower II

Approach 1: Top-down

  • Time:O(n^3)
  • Space:O(n^2)

C++

class Solution {
 public:
  int getMoneyAmount(int n) {
    // dp[i][j] := min money you need to guarantee a win of picking i..j
    dp.resize(n + 1, vector<int>(n + 1, INT_MAX));
    return getMoneyAmount(1, n);
  }

 private:
  vector<vector<int>> dp;

  int getMoneyAmount(int i, int j) {
    if (i >= j)
      return 0;
    if (dp[i][j] != INT_MAX)
      return dp[i][j];

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

    return dp[i][j];
  }
};

JAVA

class Solution {
  public int getMoneyAmount(int n) {
    // dp[i][j] := min money you need to guarantee a win of picking i..j
    dp = new int[n + 1][n + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    return getMoneyAmount(1, n);
  }

  private int[][] dp;

  private int getMoneyAmount(int i, int j) {
    if (i >= j)
      return 0;
    if (dp[i][j] != Integer.MAX_VALUE)
      return dp[i][j];

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

    return dp[i][j];
  }
}

Python

class Solution:
  def getMoneyAmount(self, n: int) -> int:
    # dp(i, j) := min money you need to guarantee a win of picking i..j
    @lru_cache(None)
    def dp(i: int, j: int) -> int:
      if i >= j:
        return 0

      ans = math.inf

      for k in range(i, j + 1):
        ans = min(ans, max(dp(i, k - 1), dp(k + 1, j)) + k)

      return ans

    return dp(1, n)

Approach 2: Bottom-up

  • Time:O(n^3)
  • Space:O(n^2)

C++

class Solution {
 public:
  int getMoneyAmount(int n) {
    // dp[i][j] := min 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];
  }
};

JAVA

class Solution {
  public int getMoneyAmount(int n) {
    // dp[i][j] := min 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];
  }
}

Python

class Solution:
  def getMoneyAmount(self, n: int) -> int:
    # dp[i][j] := min 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]