375. Guess Number Higher or Lower II

Description

The problem involves determining the minimum amount of money required to guarantee winning a guessing game. You have to guess a number between 1 and n. Every time you guess a number, and it's incorrect, you are told whether the actual number is higher or lower. You are required to find the strategy that minimizes the maximum cost incurred.

Intuition

The problem can be broken down into a decision-making scenario where you pick a number and, based on whether the number is higher or lower than the target, you either reduce the search range or increase it. The key insight is that for each guess, you want to minimize the maximum cost of the worst-case scenario, where every decision is based on guessing optimally.

Approach

We use a dynamic programming approach to break down the problem into subproblems. The dp[start][end] table stores the minimum cost required to guess a number between start and end.

• Base case: If the range is a single number (i.e., start >= end), the cost is 0 since no guessing is required.
• Recurrence: For each number in the range start to end, calculate the worst-case cost by guessing that number. The cost includes the number guessed and the maximum of the two subproblems: guessing from start to guess-1 or from guess+1 to end. The minimum of these values is taken to ensure an optimal solution.

This ensures that we always choose the strategy that minimizes the maximum possible cost.

Complexity

Time Complexity:

The time complexity is O(n^2), where n is the upper bound of the range. This is because for each range, we perform a linear scan to calculate the minimum cost.

Space Complexity:

The space complexity is O(n^2) due to the storage required for the dp table.

Code

C++

class Solution {
public:
    int getMoneyAmount(int n) {
        vector> dp(n + 1, vector(n + 1, 0));

        function calculateCost = [&](int start, int end) {
            if (start >= end) return 0;
            if (dp[start][end] != 0) return dp[start][end];

            int minCost = INT_MAX;
            for (int guess = (start + end) / 2; guess <= end; ++guess) {
                int cost = guess + max(calculateCost(start, guess - 1), calculateCost(guess + 1, end));
                minCost = min(minCost, cost);
            }

            dp[start][end] = minCost;
            return minCost;
        };

        return calculateCost(1, n);
    }
};

Python

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(n + 1)]

        def calculate_cost(start, end):
            if start >= end:
                return 0
            if dp[start][end] != 0:
                return dp[start][end]

            min_cost = float('inf')

            for guess in range((start + end) // 2, end + 1):
                cost = guess + max(calculate_cost(start, guess - 1), calculate_cost(guess + 1, end))
                min_cost = min(min_cost, cost)

            dp[start][end] = min_cost
            return min_cost

        return calculate_cost(1, n)

Java

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];

        return calculateCost(1, n, dp);
    }

    private int calculateCost(int start, int end, int[][] dp) {
        if (start >= end) return 0;

        if (dp[start][end] != 0) return dp[start][end];

        int minCost = Integer.MAX_VALUE;

        for (int guess = (start + end) / 2; guess <= end; guess++) {
            int cost = guess + Math.max(calculateCost(start, guess - 1, dp), calculateCost(guess + 1, end, dp));
            minCost = Math.min(minCost, cost);
        }

        dp[start][end] = minCost;
        return minCost;
    }
}

JavaScript

var getMoneyAmount = function (n) {

    let dp = Array(n + 1).fill(0).map(() => Array(n + 1).fill(0));

    function calculateCost(start, end) {

        if (start >= end) {
            return 0;
        }

        if (dp[start][end] !== 0) {
            return dp[start][end];
        }

        let minCost = Infinity;

        for (let guess = Math.floor((start + end) / 2); guess <= end; guess++) {

            let cost = guess + Math.max(calculateCost(start, guess - 1), calculateCost(guess + 1, end));

            minCost = Math.min(minCost, cost);
        }

        dp[start][end] = minCost;
        return minCost;
    }

    return calculateCost(1, n);
};