Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Optimization Recursion
DSA

Optimization Recursion

Learn how recursive solutions can be optimized using memoization, pruning, and better state representation.

Recognition Cheat Sheet

If you see…Think…
Minimum cost/pathMin recursion
Maximum profit/valueMax recursion
Best possible answerOptimization recursion
Include or excludeChoose max/min of both
Multiple pathsTry all → take best

Main Trigger

“Find the minimum/maximum among all possible choices” → Optimization Recursion

The Basic Idea

At every step, there are multiple choices.

Min-coins is the classic: try every coin as a branch and let the minimum bubble up (watch the dead f(-1) branch get pruned):

Coin Change (Fewest Coins)

Find the minimum number of coins that sum to a target amount.

Each call branches on every coin: take it and recurse on amount − coin, returning 1 + that result; a negative amount returns ∞ (overshoot) and 0 coins is the base case. The minimum over all branches wins; memoization removes repeated subproblems.

TREE VISUALIZER
Steps –
f(3)f(1)f(2)f(-1)✗f(0)✓f(0)✓f(1)
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        minCoins(amount):
                      
                        2
                          if amount == 0: return 0     // done!
                      
                        3
                          if amount < 0: return ∞      // overshoot
                      
                        4
                          best = ∞
                      
                        5
                          for c in coins:
                      
                        6
                            best = min(best, 1 + minCoins(amount - c))
                      
             Choice
            /      \
        Option 1   Option 2
           ↓          ↓
        Solve       Solve
           \          /
            Best result

For maximum:

Math.max(choice1, choice2)

For minimum:

Math.min(choice1, choice2)

1. Generic Optimization Template

Java

public int optimize(int[] nums, int index) {

    if (index >= nums.length)
        return 0;

    int take =
        nums[index] + optimize(nums, index + 1);

    int skip =
        optimize(nums, index + 1);

    return Math.max(take, skip);
}
def optimize(nums, index):

    if index >= len(nums):
        return 0

    take = nums[index] + optimize(nums, index + 1)

    skip = optimize(nums, index + 1)

    return max(take, skip)
int optimize(vector<int>& nums, int index) {

    if (index >= (int)nums.size())
        return 0;

    int take = nums[index] + optimize(nums, index + 1);

    int skip = optimize(nums, index + 1);

    return max(take, skip);
}
function optimize(nums, index) {

  if (index >= nums.length)
    return 0;

  const take = nums[index] + optimize(nums, index + 1);

  const skip = optimize(nums, index + 1);

  return Math.max(take, skip);
}

Pattern

Make choices
    ↓
Recurse
    ↓
Compare results
    ↓
Return best

Recognition

Multiple choices + need the best result → Optimization Recursion

2. Minimum Path Sum

At every cell, choose between:

From above
From left

Then take the smaller cost.

Java

public int minPathSum(int[][] grid) {
    return solve(grid, 0, 0);
}

private int solve(
        int[][] grid,
        int i,
        int j) {

    if (i == grid.length - 1 &&
        j == grid[0].length - 1) {
        return grid[i][j];
    }

    if (i >= grid.length ||
        j >= grid[0].length) {
        return Integer.MAX_VALUE;
    }

    int down =
        solve(grid, i + 1, j);

    int right =
        solve(grid, i, j + 1);

    return grid[i][j] +
           Math.min(down, right);
}
def min_path_sum(grid):
    return solve(grid, 0, 0)

def solve(grid, i, j):
    if i == len(grid) - 1 and j == len(grid[0]) - 1:
        return grid[i][j]

    if i >= len(grid) or j >= len(grid[0]):
        return float('inf')

    down = solve(grid, i + 1, j)

    right = solve(grid, i, j + 1)

    return grid[i][j] + min(down, right)
int minPathSum(vector<vector<int>>& grid) {
    return solve(grid, 0, 0);
}

int solve(vector<vector<int>>& grid, int i, int j) {
    if (i == (int)grid.size() - 1 && j == (int)grid[0].size() - 1)
        return grid[i][j];

    if (i >= (int)grid.size() || j >= (int)grid[0].size())
        return INT_MAX;

    int down = solve(grid, i + 1, j);

    int right = solve(grid, i, j + 1);

    return grid[i][j] + min(down, right);
}
function minPathSum(grid) {
  return solve(grid, 0, 0);
}

function solve(grid, i, j) {
  if (i === grid.length - 1 && j === grid[0].length - 1)
    return grid[i][j];

  if (i >= grid.length || j >= grid[0].length)
    return Infinity;

  const down = solve(grid, i + 1, j);

  const right = solve(grid, i, j + 1);

  return grid[i][j] + Math.min(down, right);
}

Recognition

Minimum path/cost + multiple possible paths → Min recursion

3. Maximum Value — Include / Exclude

A common optimization pattern is deciding whether to take an element.

Example:

Maximum sum of elements without choosing adjacent elements.

Java

public int maxSum(int[] nums) {
    return solve(nums, 0);
}

private int solve(int[] nums, int i) {

    if (i >= nums.length)
        return 0;

    int take =
        nums[i] + solve(nums, i + 2);

    int skip =
        solve(nums, i + 1);

    return Math.max(take, skip);
}
def max_sum(nums):
    return solve(nums, 0)

def solve(nums, i):
    if i >= len(nums):
        return 0

    take = nums[i] + solve(nums, i + 2)

    skip = solve(nums, i + 1)

    return max(take, skip)
int maxSum(vector<int>& nums) {
    return solve(nums, 0);
}

int solve(vector<int>& nums, int i) {
    if (i >= (int)nums.size())
        return 0;

    int take = nums[i] + solve(nums, i + 2);

    int skip = solve(nums, i + 1);

    return max(take, skip);
}
function maxSum(nums) {
  return solve(nums, 0);
}

function solve(nums, i) {
  if (i >= nums.length)
    return 0;

  const take = nums[i] + solve(nums, i + 2);

  const skip = solve(nums, i + 1);

  return Math.max(take, skip);
}

The two choices are:

Take
 ↓
Skip next element

OR

Skip
 ↓
Move to next element

Recognition

Take/skip + maximize result → Include/Exclude optimization

4. Minimum Coins

For each coin, try using it and choose the minimum number of coins.

Java

public int coinChange(int[] coins, int amount) {
    int result = solve(coins, amount);

    return result == Integer.MAX_VALUE
        ? -1
        : result;
}

private int solve(
        int[] coins,
        int amount) {

    if (amount == 0)
        return 0;

    if (amount < 0)
        return Integer.MAX_VALUE;

    int best = Integer.MAX_VALUE;

    for (int coin : coins) {
        int result =
            solve(coins, amount - coin);

        if (result != Integer.MAX_VALUE)
            best = Math.min(best, result + 1);
    }

    return best;
}
def coin_change(coins, amount):
    result = solve(coins, amount)

    return -1 if result == float('inf') else result

def solve(coins, amount):
    if amount == 0:
        return 0

    if amount < 0:
        return float('inf')

    best = float('inf')

    for coin in coins:
        result = solve(coins, amount - coin)

        if result != float('inf'):
            best = min(best, result + 1)

    return best
int coinChange(vector<int>& coins, int amount) {
    int result = solve(coins, amount);

    return result == INT_MAX ? -1 : result;
}

int solve(vector<int>& coins, int amount) {
    if (amount == 0)
        return 0;

    if (amount < 0)
        return INT_MAX;

    int best = INT_MAX;

    for (int coin : coins) {
        int result = solve(coins, amount - coin);

        if (result != INT_MAX)
            best = min(best, result + 1);
    }

    return best;
}
function coinChange(coins, amount) {
  const result = solve(coins, amount);

  return result === Infinity ? -1 : result;
}

function solve(coins, amount) {
  if (amount === 0)
    return 0;

  if (amount < 0)
    return Infinity;

  let best = Infinity;

  for (const coin of coins) {
    const result = solve(coins, amount - coin);

    if (result !== Infinity)
      best = Math.min(best, result + 1);
  }

  return best;
}

Recognition

Minimum number of choices needed to reach a target → Min recursion

5. Maximum / Minimum with Memoization

Plain recursion often repeats the same states.

solve(5)
 ├── solve(4)
 │    ├── solve(3)
 │    └── solve(2)
 └── solve(3)  ← repeated

Memoization stores the answer.

Java

public int maxSum(int[] nums) {
    int[] memo = new int[nums.length];
    Arrays.fill(memo, -1);

    return solve(nums, 0, memo);
}

private int solve(
        int[] nums,
        int i,
        int[] memo) {

    if (i >= nums.length)
        return 0;

    if (memo[i] != -1)
        return memo[i];

    int take =
        nums[i] + solve(nums, i + 2, memo);

    int skip =
        solve(nums, i + 1, memo);

    return memo[i] =
        Math.max(take, skip);
}
def max_sum(nums):
    memo = [-1] * len(nums)

    return solve(nums, 0, memo)

def solve(nums, i, memo):
    if i >= len(nums):
        return 0

    if memo[i] != -1:
        return memo[i]

    take = nums[i] + solve(nums, i + 2, memo)

    skip = solve(nums, i + 1, memo)

    memo[i] = max(take, skip)
    return memo[i]
int maxSum(vector<int>& nums) {
    vector<int> memo(nums.size(), -1);

    return solve(nums, 0, memo);
}

int solve(vector<int>& nums, int i, vector<int>& memo) {
    if (i >= (int)nums.size())
        return 0;

    if (memo[i] != -1)
        return memo[i];

    int take = nums[i] + solve(nums, i + 2, memo);

    int skip = solve(nums, i + 1, memo);

    return memo[i] = max(take, skip);
}
function maxSum(nums) {
  const memo = new Array(nums.length).fill(-1);

  return solve(nums, 0, memo);
}

function solve(nums, i, memo) {
  if (i >= nums.length)
    return 0;

  if (memo[i] !== -1)
    return memo[i];

  const take = nums[i] + solve(nums, i + 2, memo);

  const skip = solve(nums, i + 1, memo);

  return (memo[i] = Math.max(take, skip));
}

Recognition

Optimization recursion + repeated states → Add memoization / DP

Optimization Recursion Pattern Evolution

Basic choices
    ↓
Include / Exclude
    ↓
Min / Max result
    ↓
Repeated states
    ↓
Memoization / Dynamic Programming

Common Mistakes

1. Using the wrong comparison

For minimum:

Math.min(a, b)

For maximum:

Math.max(a, b)

2. Wrong value for invalid paths

For minimum:

Integer.MAX_VALUE

For maximum:

Integer.MIN_VALUE

These prevent invalid paths from becoming the answer.

3. Forgetting the current value

For a path problem:

return grid[i][j] + Math.min(down, right);

The current cell must be included in the result.

4. Ignoring repeated states

If the same recursive state is calculated many times:

Recursion → Memoization → DP

Don’t keep the exponential solution if the state can be cached.

Pattern Summary

Minimum path
→ Min recursion

Maximum value/profit
→ Max recursion

Take / Skip
→ Include + Exclude

Minimum choices
→ Try all choices + Math.min()

Repeated states
→ Memoization / DP

Quick Rule

Try all choices → calculate each result → return the minimum or maximum.

My Private Notes

Notes are auto-saved locally to this device.