Dare2Solve
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.
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.
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
.
start >= end
), the cost is 0 since no guessing is required.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.
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.
The space complexity is O(n^2) due to the storage required for the dp
table.
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
function<int(int, int)> 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);
}
};
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)
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;
}
}
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);
};