375.Guess-Number-Higher-or-Lower-II

375. Guess Number Higher or Lower II

题目地址

https://leetcode.com/problems/guess-number-higher-or-lower-ii/

题目描述

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:
n = 10, I pick 8.
First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.
You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

代码

Approach #1 Recursion [Time Lmit Exceeded]

Time: O(N!) && Space: O(N)

class Solution {
  public int getMoneyAmount(int n) {
            return calculate(1, n);
  }

  private int claculate(int low, int high) {
    if (low >= high)        return 0;
    int minres = Integer.MAX_VALUE;
    int mid = (low + high) / 2;
    for (int i = mid; i <= high; i++) {
      int res = i + Math.max(calculate(i+1, high), calculate(low, i - 1));
      minres = Math.min(res, minres);
    }
    return minres;
  }
}

Approach #2 Recursion with memo

class Solution {
  public int getMoneyAmount(int n) {
    int[][] memo = new int[n+1][n+1];
    return calculate(memo, 1, n);
  }

  private int calculate(int[][] memo, int start, int end) {
    if (start >= end)        return 0;
    if (memo[start][end] != 0)        return memo[start][end];
    int res = Integer.MAX_VALUE;
    int mid = (start + end) / 2; // from i = start to end
    for (int i = mid; i <= end; i++) {
      int localMax = i + Math.max(calculate(memo, start, i - 1), calculate(memo, i+1, end));
      res = Math.min(res, localMax);
    }
    memo[start][end] = res;
    return res;
  }
}

Approach #3 DP Bottom Up

Time O(n^3) Space O(N^2)

class Solution {
  public int getMoneyAmount(int n) {
    int[][] dp = new int[n + 1][n + 1];
    for (int len = 2; len <= n; len++) {
      for (int start = 1; start + len - 1 <= n; start++) {
        int end = start + len - 1;
        int minres = Integer.MAX_VALUE;
        for (int piv = start; piv < end; piv++) {
          int res = piv + Math.max(dp[start][piv-1], dp[piv+1][end]);
          minres = Math.min(res, minres);
        }
        dp[start][end] = minres;
      }
    }
    return dp[1][n];
  }
}

Approach #4 Better Approach Using DP

public class Solution {
  public int getMoneyAmount(int n) {
    int[][] dp = new int[n + 1][n + 1];
    for (int len = 2; len <= n; len++) {
      for (int start = 1; start + len - 1 <= n; start++) {
        int end = start + len - 1;
        int mid = start + (len - 1) / 2;
        int minres = Integer.MAX_VALUE;
        for (int piv = mid; piv < end; piv++) {
            int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][end]);
            minres = Math.min(res, minres);
        }
        dp[start][end] = minres;
      }
    }
    return dp[1][n];
  }
}