Guess Number Higher Or Lower II Problem


Description

LeetCode Problem 375.

We are playing the Guessing Game. The game will work as follows:

  • I pick a number between1andn.
  • You guess a number.
  • If you guess the right number, you win the game.
  • If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
  • Every time you guess a wrong numberx, you will payxdollars. If you run out of money, you lose the game.

Given a particularn, returnthe minimum amount of money you need toguarantee a win regardless of what number I pick.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1,10]. Guess 7.
- If this is my number, your total is $0. Otherwise, you pay $7.
- If my number is higher, the range is [8,10]. Guess 9.
- If this is my number, your total is $7. Otherwise, you pay $9.
- If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
- If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
- If my number is lower, the range is [1,6]. Guess 3.
- If this is my number, your total is $7. Otherwise, you pay $3.
- If my number is higher, the range is [4,6]. Guess 5.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
- If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
- If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
- If my number is lower, the range is [1,2]. Guess 1.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

Example 2:

1
2
3
Input: n = 1
Output: 0
Explanation:There is only one possible number, so you can guess 1 and not have to pay anything.

Example 3:

1
2
3
4
5
6
7
Input: n = 2
Output: 1
Explanation:There are two possible numbers, 1 and 2.
- Guess 1.
- If this is my number, your total is $0. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

Constraints:

  • 1 <= n <= 200


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
        for(int len=2; len<=n; ++len){
            for(int begin=0; begin<=n-len; ++begin){
                
                int end = begin + len;
                for(int i=begin; i<end; ++i){
                    int numPicked = i+1;
                    if(i == begin){
                        dp[begin][end] = numPicked + dp[begin+1][end];
                    } else {
                        dp[begin][end] = min(dp[begin][end], max(dp[begin][i], dp[i+1][end]) + numPicked);
                    }
                    
                }
            }
        }

        return dp[0][n];
    }
};




Related Posts

Valid Permutations For DI Sequence Problem

LeetCode 903. You are given a string s of length...

Tallest Billboard Problem

LeetCode 956. You are installing a billboard and want it...

Sum Of Subarray Minimums Problem

LeetCode 907. Given an array of integers arr, find the...

Stone Game Problem

LeetCode 877. Alice and Bob play a game with piles...

Split Array With Same Average Problem

LeetCode 805. You are given an integer array nums.

Soup Servings Problem

LeetCode 808. There are two types of soup, type A...