首页 > itarticle > guess number higher or lower ii

guess number higher or lower ii

admin 11月 12, 2020 0

Description

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.

Examples:
Given 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.
So when n = ｀10, return16`

Solution

Applied:

1. Min-max Algorithm
2. Dynamic Programming

Everytime you guess a number, the decision splits into two parts. For example, when you want to solve money from start to end, you picked i, and then your current pay is max(f(start, end), f(start, end), f(start, end) = i + f(start, i - 1) + f(i + 1, end)), and you can count i from start to end, which is mean you must choose the minimal value from all conditions.

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 * @param n an integer
 * @return how much money you need to have to guarantee a win
 */
public int (int n) {
    // Write your code here
    int[][] money = new int[n + 1][n + 1];
    return solve(money, 1, n);
}
private int solve(int[][] a, int start, int end) {
    if (start >= end) return 0;
    if (a[start][end] != 0) return a[start][end];
    a[start][end] = Integer.MAX_VALUE;
    for (int i = start; i <= end; i++) {
        a[start][end] = Math.min(a[start][end], i + Math.max(solve(a, start, i - 1), solve(a, i + 1, end)));
    }
    return a[start][end];
}

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
public class Solution {
    public int (int n) {
        int[][] dp = new int[n+1][n+1];
        for (int L = n - 1; L > 0; L--) {
			for (int R = L + 1; R <= n; R++) {
				dp[L][R] = 0x7FFFFFFF; //INT_MAX
				for (int i = L; i < R; i++) {
					dp[L][R] = Math.min(dp[L][R], i + Math.max(dp[L][i - 1], dp[i + 1][R]));
				}
			}
		}
		return dp[1][n];
    }
}

Reference Resource

细语呢喃’s blog

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能