Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

375. Guess Number Higher or Lower II

Time: $O(n^3)$

Space: $O(n^2)$

			


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];
  }
};




			


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];
  }
}




			


class Solution:
  def getMoneyAmount(self, n: int) -> int:
    # Dp(i, j) := min money you need to guarantee a win of picking i..j
    @functools.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)