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 <stdio.h>
2#include <string.h>
3
4int getMoneyAmount(int n) {
5 int dp[201][201] = {0};
6
7 for (int len = 2; len <= n; ++len) {
8 for (int start = 1; start <= n - len + 1; ++start) {
9 int minCost = INT_MAX;
10 for (int piv = start; piv < start + len - 1; ++piv) {
11 int cost = piv + (piv+1 <= start+len-1 ? dp[piv+1][start+len-1] : 0);
12 cost = piv > start ? cost + dp[start][piv-1] : cost;
13 minCost = minCost < cost ? minCost : cost;
14 }
15 dp[start][start + len - 1] = minCost;
16 }
17 }
18 return dp[1][n];
19}
20
21int main() {
22 int n = 10;
23 printf("Minimum amount of money to guarantee a win is: %d", getMoneyAmount(n));
24 return 0;
25}The code defines a function getMoneyAmount that uses a 2D array dp to store the minimum cost for each subproblem. It iteratively calculates the minimum cost for increasing intervals, considering each number in the interval as a potential guess and calculating the worst-case cost. The main program calls this function with n = 10 and outputs the result.
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#include <vector>
using namespace std;
vector<vector<int>> dp;
int minCost(int start, int end) {
if (start >= end) return 0;
if (dp[start][end] != -1) return dp[start][end];
int res = INT_MAX;
for (int piv = start; piv <= end; ++piv) {
int cost = piv + max(minCost(start, piv - 1), minCost(piv + 1, end));
res = min(res, cost);
}
return dp[start][end] = res;
}
int getMoneyAmount(int n) {
dp.assign(n+1, vector<int>(n+1, -1));
return minCost(1, n);
}
int main() {
cout << "Minimum amount to guarantee a win: " << getMoneyAmount(10) << endl;
return 0;
}In this C++ code, the minCost recursive function leverages memoization to prevent redundant calculations. The getMoneyAmount function initializes a 2D vector dp with entries set to -1, indicating unsolved subproblems. The recursion resolves all subproblems, caching results for efficiency.