Guess Number Higher or Lower II
We need to solve a game where we guess a number between 1 and n. Each wrong guess costs the amount equal to the guessed number. The goal is to find the minimum amount of money needed to guarantee a win regardless of which number is selected.
Brute-Force Recursion
class Solution {
public:
int calculateMinCost(int n) {
return solve(1, n);
}
private:
int solve(int left, int right) {
if (left >= right)
return 0;
int minCost = INT_MAX;
for (int guess = left; guess <= right; guess++) {
int currentCost = guess + max(solve(left, guess - 1), solve(guess + 1, right));
minCost = min(minCost, currentCost);
}
return minCost;
}
};
This approach uses a recursive divide-and-conquer strategy to find the optimal guess. For each possible guess, it calculates the worst-case scenario and selects the guess that minimizes this maximum cost. The algorithm transforms the problem into finding a minimax solution.
Memoization Recursion
class Solution {
public:
int calculateMinCost(int n) {
memset(cache, 0, sizeof(cache));
return solve(1, n);
}
private:
int cache[201][201];
int solve(int left, int right) {
if (left >= right)
return 0;
if (cache[left][right] != 0)
return cache[left][right];
int minCost = INT_MAX;
for (int guess = left; guess <= right; guess++) {
int currentCost = guess + max(solve(left, guess - 1), solve(guess + 1, right));
minCost = min(minCost, currentCost);
}
cache[left][right] = minCost;
return minCost;
}
};
This optimized version uses a 2D array called cache to store results of previously computed subproblems. This technique, known as memoization, avoids redundant calculations by checking if a subproblem has been solved before. This significantly improves efficiency while maintaining the recursive approach.
Dynamic Programming
class Solution {
public:
int calculateMinCost(int n) {
int dp[201][201] = {0};
for (int length = 2; length <= n; length++) {
for (int start = 1; start <= n - length + 1; start++) {
int end = start + length - 1;
int minCost = INT_MAX;
for (int pivot = start; pivot < end; pivot++) {
int cost = pivot + max(dp[start][pivot - 1], dp[pivot + 1][end]);
minCost = min(minCost, cost);
}
dp[start][end] = minCost;
}
}
return dp[1][n];
}
};
The dynamic programming solution uses a bottom-up approach to fill a 2D table dp where dp[i][j] represents the minimum cost to guarantee a win for the number range [i, j]. The solution builds up from smaller subproblems to solve the entire problem iteratively.
Relationship Between Memoization Recursion and Dynamic Programming
Both memoization recursion and dynamic programming optimize solutions by avoiding redundant calculations of subproblems. They share the same core idea but differ in implementation:
- Core Idea: Both store results of subproblems to avoid recomputation.
- State Representation: Both use a 2D array to store intermediate results for subproblems.
- State Transition: Both follow the same state transition equation:
dp[left][right] = min(max(dp[left][i-1], dp[i+1][right]) + i)for all valid i.
The key differences are:
- Approach: Memoization uses a top-down approach, while dynamic programming uses a bottom-up approach.
- Computation Order: Memoization computes subproblems on-demand, while dynamic programming computes all subproblems systematically.
- Space Utilization: Memoization uses additional stack space for recursion, while dynamic programming primarily uses the allocated array space.
To convert memoization recursion to dynamic programming:
- Identify states and state transition equations from the recursive function.
- Determine the appropriate traversal order to ensure dependencies are resolved.
- Initialize the DP table based on base cases from the recursive solution.
- Replace recursive calls with iterative table updates.
- Extract the final result from the DP table.
Longest Incrreasing Path in a Matrix
Given an m x n matrix, we need to find the length of the longest increasing path. From each cell, we can move to adjacent cells (up, down, left, right) with strictly greater values.
Brute-Force Recursion Approach 1
class Solution {
public:
int findLongestPath(vector<vector>>& grid) {
rows = grid.size();
cols = grid[0].size();
maxPath = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
explore(grid, i, j, 1);
}
}
return maxPath;
}
private:
int rows, cols;
int maxPath;
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void explore(const vector<vector>>& grid, int i, int j, int currentLength) {
maxPath = max(maxPath, currentLength);
for (int d = 0; d < 4; d++) {
int nextI = i + directions[d][0];
int nextJ = j + directions[d][1];
if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols &&
grid[nextI][nextJ] > grid[i][j]) {
explore(grid, nextI, nextJ, currentLength + 1);
}
}
}
};</vector></vector>
This approach explores all possible paths from each cell, keeping track of the maximum path length found. The recursive function explore traverses all valid adjacent cells with greater values. Each node in the recursion graph represents a position and path length combination, with no repeated nodes.
Brute-Force Recursion Approach 2
class Solution {
public:
int findLongestPath(vector<vector>>& grid) {
rows = grid.size();
cols = grid[0].size();
int maxLength = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maxLength = max(maxLength, computePath(grid, i, j));
}
}
return maxLength;
}
private:
int rows, cols;
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int computePath(const vector<vector>>& grid, int i, int j) {
int maxSubPath = 0;
for (int d = 0; d < 4; d++) {
int nextI = i + directions[d][0];
int nextJ = j + directions[d][1];
if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols &&
grid[nextI][nextJ] > grid[i][j]) {
maxSubPath = max(maxSubPath, computePath(grid, nextI, nextJ));
}
}
return maxSubPath + 1;
}
};</vector></vector>
This approach defines computePath(i, j) as the length of the longest increasing path starting from position (i, j). The value for each position depends on the maximum value from its valid adjacent positions. This creates overlapping subproblems in the recursion graph, making it suitable for memoization.
Memoization Recursion
class Solution {
public:
int findLongestPath(vector<vector>>& grid) {
rows = grid.size();
cols = grid[0].size();
memset(memo, 0, sizeof(memo));
int maxLength = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maxLength = max(maxLength, computePath(grid, i, j));
}
}
return maxLength;
}
private:
int rows, cols;
int memo[201][201];
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int computePath(const vector<vector>>& grid, int i, int j) {
if (memo[i][j] != 0)
return memo[i][j];
int maxSubPath = 0;
for (int d = 0; d < 4; d++) {
int nextI = i + directions[d][0];
int nextJ = j + directions[d][1];
if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols &&
grid[nextI][nextJ] > grid[i][j]) {
maxSubPath = max(maxSubPath, computePath(grid, nextI, nextJ));
}
}
memo[i][j] = maxSubPath + 1;
return maxSubPath + 1;
}
};</vector></vector>
This solution adds memoization to store computed path lengths for each position. Before computing the path length for a position, it checks if the result is already in the memo table. If not, it computes the result and stores it for future use. This eliminates redundant calculations and significantly improves performance.
Dynamic Programming
class Solution {
public:
int findLongestPath(vector<vector>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int rows = grid.size();
int cols = grid[0].size();
vector<vector>> dp(rows, vector<int>(cols, 1));
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool updated = true;
while (updated) {
updated = false;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
for (int d = 0; d < 4; d++) {
int nextI = i + directions[d][0];
int nextJ = j + directions[d][1];
if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols &&
grid[nextI][nextJ] > grid[i][j]) {
if (dp[i][j] < dp[nextI][nextJ] + 1) {
dp[i][j] = dp[nextI][nextJ] + 1;
updated = true;
}
}
}
}
}
}
int maxLength = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maxLength = max(maxLength, dp[i][j]);
}
}
return maxLength;
}
};</int></vector></vector>
The dynamic programming approach initializes a DP table where each cell starts with a path length of 1 (the cell itself). It then iteratively updates the table until no further improvements can be made. For each cell, it checks all adjacent cells with greater values and updates the path length if a longer path is found. This process continues until the entire table stabilizes.
The key insight is that for any position (i, j), its path length depends on adjacent positions (x, y) where grid[x][y] > grid[i][j]. The DP relation is: dp[i][j] = max(dp[x][y]) + 1 for all valid adjacent positions with greater values.