Guessing Game: Minimum Guarantee Amount

Problem Description

We are playing a game where you have to guess a number I've picked between 1 and n. If you guess wrong, I tell you if my number is higher or lower, and you pay an amount equal to your guess. The goal is to determine the minimum amount of money you need to guarantee a win, regardless of the number I pick.

Naive Approach (Brute Force with Recursion)

A brute-force approach involves trying every possible guess at each step and recursively calculating the worst-case cost for each choice. This will have overlapping subproblems, so we'll show the dynamic programming approach next.

Optimal Approach (Dynamic Programming)

We can use dynamic programming to solve this problem efficiently. Let dp[i][j] represent the minimum amount of money needed to guarantee a win when the range of possible numbers is from i to j (inclusive).

1. Base Case: dp[i][i] = 0 (If there's only one number, you can guess it directly without any cost).
2. Recursive Relation: For a range [i, j], we can iterate through all possible guesses k from i to j. For each k, the worst-case cost would be k + max(dp[i][k-1], dp[k+1][j]). We take the minimum of these worst-case costs for all k to find dp[i][j].

dp[i][j] = min(k + max(dp[i][k-1], dp[k+1][j])) for k in range(i, j + 1)

Code Implementation (Python)

def getMoneyAmount(n):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j + 1):
                dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1] if k > i else 0, dp[k + 1][j] if k < j else 0))

    return dp[1][n]

Example Walkthrough (n = 10)

As shown in example 1, to guarantee a win for n = 10, the minimum amount of money needed is 16.

The algorithm calculates the dp table by considering all subranges:

• Ranges of length 2: [1, 2], [2, 3], ..., [9, 10]
• Ranges of length 3: [1, 3], [2, 4], ..., [8, 10]
• ... and so on, up to the range [1, 10]

For each range, it tries all possible guesses and uses the recursive relation mentioned to find the minimum cost.

Edge Cases

• n = 1: The result is 0 because you can guess the number directly.
• n = 2: The result is 1. Guess 1. If it's wrong, the number is 2 and you pay 1.

Time and Space Complexity

• Time Complexity: O(n^3), because we have a nested loop for filling the dp table (O(n^2)), and an inner loop for calculating the minimum cost for each cell (O(n)).
• Space Complexity: O(n^2), because we store the results in a 2D dp table of size n x n.