375. Guess Number Higher or Lower II – Leetcode Solutions

Example 1:

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:

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:

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.

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        # Initialize a 2D DP table with zeros, size (n+1) x (n+1) because of 1-based indexing
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        
        # Fill the DP table for all ranges [i, j] where j > i
        for length in range(2, n + 1):  # length of range, starting from 2 up to n
            for i in range(1, n - length + 2):
                j = i + length - 1
                dp[i][j] = float('inf')  # Initialize with a high cost
                
                # Try every possible guess `x` between `i` and `j`
                for x in range(i, j):
                    # The cost when picking `x` as the guess
                    cost = x + max(dp[i][x - 1], dp[x + 1][j])
                    # Minimize the cost for this range
                    dp[i][j] = min(dp[i][j], cost)
        
        # The answer for the whole range [1, n] will be stored in dp[1][n]
        return dp[1][n]

class Solution {
public:
    int getMoneyAmount(int n) {
        // dp[i][j] will store the minimum cost to guarantee a win in range [i, j]
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        
        // Calculate the DP values for all subranges
        for (int len = 2; len <= n; ++len) { // len is the length of the range
            for (int i = 1; i <= n - len + 1; ++i) {
                int j = i + len - 1;
                dp[i][j] = INT_MAX; // Start with a large value
                for (int k = i; k <= j; ++k) {
                    int cost = k + max(k > i ? dp[i][k - 1] : 0, k < j ? dp[k + 1][j] : 0);
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }
        
        return dp[1][n]; // Minimum cost to guarantee a win for range [1, n]
    }
};

var getMoneyAmount = function(n) {
    // Create a 2D array to store the minimum costs
    const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

    // Function to find minimum cost between two numbers (start and end)
    const calculateCost = (start, end) => {
        if (start >= end) return 0; // No cost if there's only one number or none to guess

        if (dp[start][end] !== 0) return dp[start][end]; // Return cached result if available

        let minCost = Infinity;

        // Try each possible number (k) as the first guess and calculate the worst-case cost
        for (let k = start; k <= end; k++) {
            const costIfWrong = k + Math.max(calculateCost(start, k - 1), calculateCost(k + 1, end));
            minCost = Math.min(minCost, costIfWrong);
        }

        dp[start][end] = minCost; // Store the minimum cost in dp array
        return minCost;
    };

    return calculateCost(1, n); // Start with the range [1, n]
};

class Solution {
    public int getMoneyAmount(int n) {
        // Initialize a DP table where dp[i][j] represents the minimum cost to guess the correct number in the range [i, j].
        int[][] dp = new int[n + 1][n + 1];
        
        // Fill the DP table from smaller ranges to larger ranges
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;
                dp[start][end] = Integer.MAX_VALUE; // Initialize with a large number
                
                // Try guessing each number in the range [start, end]
                for (int k = start; k < end; k++) {
                    // Cost if we choose `k` as the pivot and it's incorrect
                    int cost = k + Math.max(dp[start][k - 1], dp[k + 1][end]);
                    
                    // We want the minimum cost across all choices of `k`
                    dp[start][end] = Math.min(dp[start][end], cost);
                }
            }
        }
        
        // The answer for the range [1, n] is stored in dp[1][n]
        return dp[1][n];
    }
}