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.

1
2
3
4
5
6
7
8
9
10
11
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.

Hint:

  1. The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.
  2. Take a small example (n = 3). What do you end up paying in the worst case?
  3. Check out this article if you’re still stuck.
  4. The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
  5. As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?

java


https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation

Simple DP solution with explanation~~

For each number x in range[i~j]
we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}

–> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.

then we get DP([i~ j]) = min{xi, … ,xj }

–> // this min makes sure that you are minimizing your cost.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int getMoneyAmount(int n) {
int[][] table = new int[n+1][n+1];
return DP(table, 1, n);
}

int DP(int[][] t, int s, int e){
if(s >= e) return 0;
if(t[s][e] != 0) return t[s][e];
int res = Integer.MAX_VALUE;
for(int x=s; x<=e; x++){
int tmp = x + Math.max(DP(t, s, x-1), DP(t, x+1, e));
res = Math.min(res, tmp);
}
t[s][e] = res;
return res;
}
}

Here is a bottom up solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int getMoneyAmount(int n) {
int[][] table = new int[n+1][n+1];
for(int j=2; j<=n; j++){
for(int i=j-1; i>0; i--){
int globalMin = Integer.MAX_VALUE;
for(int k=i+1; k<j; k++){
int localMax = k + Math.max(table[i][k-1], table[k+1][j]);
globalMin = Math.min(globalMin, localMax);
}
table[i][j] = i+1==j?i:globalMin;
}
}
return table[1][n];
}
}

https://discuss.leetcode.com/topic/51358/java-dp-solution

Java DP solution

Definition of dp[i][j]: minimum number of money to guarantee win for subproblem [i, j].

Target: dp[1][n]

Corner case: dp[i][i] = 0 (because the only element must be correct)

Equation: we can choose k (i<=k<=j) as our guess, and pay price k. After our guess, the problem is divided into two subproblems. Notice we do not need to pay the money for both subproblems. We only need to pay the worst case (because the system will tell us which side we should go) to guarantee win. So dp[i][j] = min (i<=k<=j) { k + max(dp[i][k-1], dp[k+1][j]) }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int getMoneyAmount(int n) {
if (n == 1) {
return 0;
}
int[][] dp = new int[n + 1][n + 1];
for (int jminusi = 1; jminusi < n; jminusi++) {
for (int i = 0; i + jminusi <= n; i++) {
int j = i + jminusi;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j; k++) {
dp[i][j] = Math.min(dp[i][j],
k + Math.max(k - 1 >= i ? dp[i][k - 1] : 0,
j >= k + 1 ? dp[k + 1][j] : 0));
}
}
}
return dp[1][n];
}
}

https://discuss.leetcode.com/topic/51494/java-commented-dp-solution

Java commented DP solution

Big Idea: Given any n, we make a guess k. Then we break the interval [1,n] into [1,k - 1] and [k + 1,n]. The min of worst case cost can be calculated recursively as

cost[1,n] = k + max{cost[1,k - 1] + cost[k+1,n]}
Also, it takes a while for me to wrap my head around “min of max cost”. My understand is that: you strategy is the best, but your luck is the worst. You only guess right when there is no possibilities to guess wrong.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
public int getMoneyAmount(int n) {
// all intervals are inclusive
// uninitialized cells are assured to be zero
// the zero column and row will be uninitialized
// the illegal cells will also be uninitialized
// add 1 to the length just to make the index the same as numbers used
int[][] dp = new int[n + 1][n + 1]; // dp[i][j] means the min cost in the worst case for numbers (i...j)

// iterate the lengths of the intervals since the calculations of longer intervals rely on shorter ones
for (int l = 2; l <= n; l++) {
// iterate all the intervals with length l, the start of which is i. Hence the interval will be [i, i + (l - 1)]
for (int i = 1; i <= n - (l - 1); i++) {
dp[i][i + (l - 1)] = Integer.MAX_VALUE;
// iterate all the first guesses g
for (int g = i; g <= i + (l - 1); g++) {
int costForThisGuess;
// since if g is the last integer, g + 1 does not exist, we have to separate this case
// cost for [i, i + (l - 1)]: g (first guess) + max{the cost of left part [i, g - 1], the cost of right part [g + 1, i + (l - 1)]}
if (g == n) {
costForThisGuess = dp[i][g - 1] + g;
} else {
costForThisGuess = g + Math.max(dp[i][g - 1], dp[g + 1][i + (l - 1)]);
}
dp[i][i + (l - 1)] = Math.min(dp[i][i + (l - 1)], costForThisGuess); // keep track of the min cost among all first guesses
}
}
}
return dp[1][n];
}
}

Any questions, suggestions & criticism welcomed!


cpp


https://discuss.leetcode.com/topic/51487/an-o-n-2-dp-solution-quite-hard

An O(n^2) DP Solution, Quite Hard.

Algorithm description: http://artofproblemsolving.com/community/c296841h1273742

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> u(n + 2, vector<int>(n + 2));
for (int b = 2; b <= n; ++b) {
int k0 = b - 1;
deque<pair<int, int>> v;
for (int a = b - 1; a; --a) {
while (u[a][k0 - 1] > u[k0 + 1][b]) {
if (!v.empty() && v.front().second == k0) v.pop_front();
--k0;
}
int vn = a + u[a + 1][b];
while (!v.empty() && vn < v.back().first) v.pop_back();
v.emplace_back(vn, a);
int u1 = u[a][k0] + k0 + 1;
int u2 = v.front().first;
u[a][b] = u1 < u2 ? u1 : u2;
}
}
return u[1][n];
}
};

python


https://discuss.leetcode.com/topic/51356/two-python-solutions

Two Python solutions

To find out how much money I need to win the range lo..hi (the game starts with the range 1..n), I try each possible x in the range (except hi, which is pointless because hi-1 costs less and provides more information), calculate how much I need when using that x, and take the minimum of those amounts.

Bottom-up dynamic programming:

1
2
3
4
5
6
7
def getMoneyAmount(self, n):
need = [[0] * (n+1) for _ in range(n+1)]
for lo in range(n, 0, -1):
for hi in range(lo+1, n+1):
need[lo][hi] = min(x + max(need[lo][x-1], need[x+1][hi])
for x in range(lo, hi))
return need[1][n]

Top-down with memoization, subclassing dict for convenience. Simpler than bottom-up because I don’t need to specify ranges/loops for lo and hi and don’t need to think about their orders and how big my DP matrix needs to be. On the other hand, it’s slower.

Got the motivation to use tuples as indexes from @agave. I had used that myself sometimes in the past, but thought it would be very slow. Turns out it’s not that slow. I should do some timings to get a better feeling for it…

1
2
3
4
5
6
7
8
9
def getMoneyAmount(self, n):
class Need(dict):
def __missing__(self, (lo, hi)):
if lo >= hi:
return 0
ret = self[lo, hi] = min(x + max(self[lo, x-1], self[x+1, hi])
for x in range(lo, hi))
return ret
return Need()[1, n]


谢谢你,可爱的朋友。