Sponsored
Sponsored
This approach involves using dynamic programming with recursion to solve the problem. The main idea is to break the problem into subproblems: determining the cost of guessing any number within a given range. For each number in the current range, calculate the worst-case cost of guessing that number, accounting for both possibilities where the picked number is less or greater than the guessed number. Store solutions to subproblems to avoid recalculating them.
Time Complexity: O(n^3) due to the three nested loops through possible ranges and guesses.
Space Complexity: O(n^2) for storing results of subproblems.
1#include <iostream>
2#include <vector>
3#include <climits>
4using namespace std;
5
6int getMoneyAmount(int n) {
7 vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
8 for (int len = 2; len <= n; ++len) {
9 for (int start = 1; start <= n-len+1; ++start) {
10 int end = start+len-1;
11 int min_cost = INT_MAX;
12 for (int piv = start; piv <= end; ++piv) {
13 int cost = piv + max(piv-1 >= start ? dp[start][piv-1] : 0,
14 piv+1 <= end ? dp[piv+1][end] : 0);
15 min_cost = min(min_cost, cost);
16 }
17 dp[start][end] = min_cost;
18 }
19 }
20 return dp[1][n];
21}
22
23int main() {
24 int n = 10;
25 cout << "Minimum amount: " << getMoneyAmount(n) << endl;
26 return 0;
27}In this C++ solution, the idea is illustrated using a similar dynamic programming approach as in the C example. The algorithm evaluates the cost for each range of guesses incrementally, updating the dp table iteratively until the final result is obtained at dp[1][n]. This solution efficiently computes the minimum guaranteed cost.
A more advanced recursive approach with memoization achieves similar results, storing results of previously solved subproblems in a cache for fast retrieval. This is especially useful for large inputs, reducing computational overhead by avoiding repeated calculations of the same conditions and ranges.
Time Complexity: O(n^2), reduced with memoization.
Space Complexity: O(n^2), for memoizing results.
1
This recursive solution uses a helper function minCost that utilizes memoization to cache results of subproblems in a table dp. The getMoneyAmount function initializes the cache and invokes the helper for the full range from 1 to n, ensuring that calculations are only done once per subproblem.