Recursion to Dynamic Programming Conversion

• Core idea: Transform recursive solutions into iterative DP for better performance
• When to use: Recursive solutions with overlapping subproblems and optimal substructure
• Key benefits: Eliminate redundant calculations, reduce space from O(n) stack to O(n) or O(1) array
• Common pattern: Recognize memoization opportunities, then convert to bottom-up tabulation

Conversion Steps:

1. Identify base cases
2. Find recursive relation
3. Add memoization (Top-Down DP)
4. Convert to tabulation (Bottom-Up DP)
5. Optimize space if possible

---

0) Concept

0-0) When to Convert Recursion to DP

Indicators that DP is applicable:

“When you hear a problem beginning with the following statements, it’s often (though not always) a good candidate for recursion: ‘Design an algorithm to compute the nth…’, ‘Write code to list the first n…’, ‘Implement a method to compute all…’, and so on.” — Cracking the Coding Interview, 6th Edition, p.130

Requirements for DP:

1. Overlapping Subproblems: Same subproblems solved multiple times
2. Optimal Substructure: Optimal solution contains optimal solutions to subproblems
3. Memoization Opportunity: Results can be cached for reuse

Recognition Patterns:

• “Find the nth…”
• “Count ways to…”
• “Minimum/maximum…”
• “Optimize…”
• Multiple recursive calls with same parameters

0-1) Conversion Strategy

Recursion (Exponential)
    ↓
Top-Down DP (Memoization)
    ↓
Bottom-Up DP (Tabulation)
    ↓
Space-Optimized DP

Top-Down (Memoization):

• Keep recursive structure
• Add cache (memo) to store results
• Easy to implement from recursion
• Space: O(n) for memo + O(n) for call stack

Bottom-Up (Tabulation):

• Build solution iteratively
• Fill DP table from base cases up
• No recursion overhead
• Space: O(n) for DP table only

Space Optimization:

• Identify what previous states are actually needed
• Often can reduce from O(n) to O(k) where k is constant
• Example: Fibonacci only needs last 2 values

---

1) Complete Examples: Recursion → DP

1-1) Fibonacci Sequence

Problem: Compute the nth Fibonacci number where F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1.

Step 1: Naive Recursion

# Python - Naive Recursion
def fib_recursive(n):
    """
    Time: O(2^n) - exponential
    Space: O(n) - call stack depth
    """
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

// Java - Naive Recursion
public int fibRecursive(int n) {
    /**
     * time = O(2^N) - exponential
     * space = O(N) - call stack
     */
    if (n <= 1) return n;
    return fibRecursive(n-1) + fibRecursive(n-2);
}

Problem: Massive redundant calculations!

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)  <- Computed again!
│       ├── fib(1)
│       └── fib(0)
└── fib(3)      <- Computed again!
    ├── fib(2)  <- Computed again!
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

Step 2: Top-Down DP (Memoization)

# Python - Top-Down DP
def fib_memo(n, memo=None):
    """
    Time: O(n) - each subproblem solved once
    Space: O(n) - memo dict + call stack
    """
    if memo is None:
        memo = {}

    if n <= 1:
        return n

    if n in memo:
        return memo[n]

    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

// Java - Top-Down DP
public int fibMemo(int n) {
    return fibMemoHelper(n, new int[n+1]);
}

private int fibMemoHelper(int n, int[] memo) {
    /**
     * time = O(N)
     * space = O(N) - memo + call stack
     */
    if (n <= 1) return n;

    if (memo[n] != 0) return memo[n];

    memo[n] = fibMemoHelper(n-1, memo) + fibMemoHelper(n-2, memo);
    return memo[n];
}

Step 3: Bottom-Up DP (Tabulation)

# Python - Bottom-Up DP
def fib_dp(n):
    """
    Time: O(n)
    Space: O(n) - DP table
    """
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

// Java - Bottom-Up DP
public int fibDP(int n) {
    /**
     * time = O(N)
     * space = O(N)
     */
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

Step 4: Space-Optimized DP

# Python - Space Optimized
def fib_optimized(n):
    """
    Time: O(n)
    Space: O(1) - only 2 variables
    """
    if n <= 1:
        return n

    prev2, prev1 = 0, 1

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

// Java - Space Optimized
public int fibOptimized(int n) {
    /**
     * time = O(N)
     * space = O(1)
     */
    if (n <= 1) return n;

    int prev2 = 0, prev1 = 1;

    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

Summary:

Approach	Time	Space	Notes
Naive Recursion	O(2^n)	O(n)	Exponential, unusable for n>40
Memoization	O(n)	O(n) + O(n)	Easy to code, still has stack overhead
Tabulation	O(n)	O(n)	No recursion, cleaner
Space Optimized	O(n)	O(1)	Best overall

---

1-2) Climbing Stairs (LC 70)

Problem: Climbing n stairs, can climb 1 or 2 steps. How many distinct ways?

Step 1: Recursion

def climbStairs_recursive(n):
    """Time: O(2^n), Space: O(n)"""
    if n <= 2:
        return n
    return climbStairs_recursive(n-1) + climbStairs_recursive(n-2)

Step 2: Memoization

def climbStairs_memo(n, memo=None):
    """Time: O(n), Space: O(n)"""
    if memo is None:
        memo = {}

    if n <= 2:
        return n

    if n in memo:
        return memo[n]

    memo[n] = climbStairs_memo(n-1, memo) + climbStairs_memo(n-2, memo)
    return memo[n]

Step 3: Bottom-Up DP

// LC 70 - Climbing Stairs
public int climbStairs(int n) {
    /**
     * time = O(N)
     * space = O(N)
     */
    if (n <= 2) return n;

    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

Step 4: Space Optimized

public int climbStairsOptimized(int n) {
    /**
     * time = O(N)
     * space = O(1)
     */
    if (n <= 2) return n;

    int prev2 = 1, prev1 = 2;

    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

---

1-3) House Robber (LC 198)

Problem: Array of house values. Can’t rob adjacent houses. Maximum robbery amount?

Step 1: Recursion

def rob_recursive(nums, i=0):
    """
    Time: O(2^n)
    Space: O(n)
    """
    if i >= len(nums):
        return 0

    # Choice: rob current house or skip
    rob_current = nums[i] + rob_recursive(nums, i+2)
    skip_current = rob_recursive(nums, i+1)

    return max(rob_current, skip_current)

Step 2: Memoization

def rob_memo(nums, i=0, memo=None):
    """Time: O(n), Space: O(n)"""
    if memo is None:
        memo = {}

    if i >= len(nums):
        return 0

    if i in memo:
        return memo[i]

    rob_current = nums[i] + rob_memo(nums, i+2, memo)
    skip_current = rob_memo(nums, i+1, memo)

    memo[i] = max(rob_current, skip_current)
    return memo[i]

Step 3: Bottom-Up DP

// LC 198 - House Robber
public int rob(int[] nums) {
    /**
     * time = O(N)
     * space = O(N)
     */
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        // Choice: rob current + dp[i-2] OR skip current (dp[i-1])
        dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
    }

    return dp[nums.length - 1];
}

Step 4: Space Optimized

public int robOptimized(int[] nums) {
    /**
     * time = O(N)
     * space = O(1)
     */
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        int current = Math.max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

---

1-4) Coin Change (LC 322)

Problem: Array of coin denominations, target amount. Minimum coins needed?

Step 1: Recursion

def coinChange_recursive(coins, amount):
    """
    Time: O(S^n) where S = amount, n = coins
    Space: O(amount)
    """
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    min_coins = float('inf')

    for coin in coins:
        result = coinChange_recursive(coins, amount - coin)
        if result >= 0:
            min_coins = min(min_coins, result + 1)

    return min_coins if min_coins != float('inf') else -1

Step 2: Memoization

def coinChange_memo(coins, amount, memo=None):
    """Time: O(S × n), Space: O(S)"""
    if memo is None:
        memo = {}

    if amount == 0:
        return 0
    if amount < 0:
        return -1
    if amount in memo:
        return memo[amount]

    min_coins = float('inf')

    for coin in coins:
        result = coinChange_memo(coins, amount - coin, memo)
        if result >= 0:
            min_coins = min(min_coins, result + 1)

    memo[amount] = min_coins if min_coins != float('inf') else -1
    return memo[amount]

Step 3: Bottom-Up DP

// LC 322 - Coin Change
public int coinChange(int[] coins, int amount) {
    /**
     * time = O(S × N) where S = amount, N = coins
     * space = O(S)
     */
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // Infinity placeholder

    dp[0] = 0; // Base case

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

---

2) Common LeetCode Problems

Recursion → DP Conversions

Problem	Difficulty	Recursive Pattern	DP Type
LC 70	Easy	Stairs = (n-1) + (n-2)	1D DP
LC 198	Medium	Rob = max(rob, skip)	1D DP
LC 322	Medium	Min coins for amount	Unbounded knapsack
LC 509	Easy	Fibonacci	Classic
LC 746	Easy	Min cost climbing	1D DP
LC 139	Medium	Word break	String DP
LC 300	Medium	Longest increasing	Subsequence DP
LC 416	Medium	Partition subset	0/1 knapsack

---

3) Conversion Checklist

✅ Step-by-Step Guide

1. Identify Base Cases

   • What are the simplest inputs?
   • What can be returned immediately?

2. Find Recursive Relation

   • How does F(n) relate to F(n-1), F(n-2), etc.?
   • What choices/decisions are made at each step?

3. Add Memoization (Top-Down)

   • Create cache/memo structure
   • Check cache before computing
   • Store result after computing

4. Convert to Tabulation (Bottom-Up)

   • Create DP array
   • Fill base cases
   • Iterate from small to large subproblems
   • Use recurrence relation to fill table

5. Optimize Space

   • Identify which previous states are needed
   • Use variables instead of full array if possible

---

4) Interview Tips

💡 Recognition Patterns

When to suspect DP:

• “Find the nth…”
• “Count ways to…”
• “Minimum/maximum…”
• Multiple recursive calls
• Overlapping subproblems

Conversion Strategy:

1. Start with recursion (easier to understand)
2. Add memoization (quick win)
3. Convert to bottom-up if asked
4. Optimize space if time permits

🎯 Interview Talking Points

1. Why DP is better:

   • “Eliminates redundant calculations”
   • “Trades space for time”
   • “Linear time instead of exponential”

2. Top-Down vs Bottom-Up:

   • “Top-down is easier to code from recursion”
   • “Bottom-up is more efficient (no stack overhead)”
   • “Both have same time complexity”

3. Space Optimization:

   • “Only need previous k states”
   • “Can reduce from O(n) to O(k)”
   • “Common for 1D DP problems”

📊 Complexity Analysis

Approach	Typical Time	Typical Space	Notes
Naive Recursion	O(2^n)	O(n)	Unusable for n>30
Memoization	O(n)	O(n) + O(n)	Easy to code
Tabulation	O(n)	O(n)	More efficient
Space Optimized	O(n)	O(1) or O(k)	Best overall

---

Summary

Core Principles:

• ✅ Recursion → Memoization → Tabulation → Space Optimization
• ✅ Look for overlapping subproblems
• ✅ Memoization keeps recursive structure, adds cache
• ✅ Tabulation builds solution iteratively from base cases

When to Use:

• “Find the nth…” problems
• Optimization problems (min/max)
• Counting problems (number of ways)
• Problems with choices at each step

Interview Strategy:

1. Start with recursive solution
2. Identify overlapping subproblems
3. Add memoization
4. Convert to bottom-up if needed
5. Optimize space if possible

Key Insight: Every DP problem can be solved recursively first, then optimized with memoization/tabulation.

LC Examples

2-1) House Robber (LC 198) — Recursion → Memoization → DP

Cannot rob two adjacent houses; dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

// LC 198 - House Robber
// IDEA: DP — dp[i] = max money robbing up to house i
// time = O(N), space = O(1)
public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    int prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < nums.length; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2-2) Word Break (LC 139) — Top-down Recursion → DP

dp[i] = true if s[0…i] can be segmented using wordDict.

// LC 139 - Word Break
// IDEA: DP — dp[i] means s[0..i-1] can be segmented
// time = O(N^2), space = O(N)
public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
    return dp[n];
}

2-3) Edit Distance (LC 72) — 2D DP (String → String)

dp[i][j] = min operations to convert s1[0…i] to s2[0…j].

// LC 72 - Edit Distance
// IDEA: 2D DP — dp[i][j] = min ops to convert word1[0..i-1] to word2[0..j-1]
// time = O(M*N), space = O(M*N)
public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (word1.charAt(i-1) == word2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
    return dp[m][n];
}

2-4) Fibonacci Number (LC 509) — Recursion → Memoization → DP → O(1)

Classic example showing all 4 levels of optimization from naive recursion.

// LC 509 - Fibonacci Number
// IDEA: Iterative DP — O(N) time, O(1) space (vs O(2^N) naive recursion)
// time = O(N), space = O(1)
public int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2-5) Unique Paths (LC 62) — 2D Recursion → DP

Recursion f(i,j) = f(i-1,j) + f(i,j-1) → bottom-up DP with row compression.

// LC 62 - Unique Paths
// IDEA: DP with 1D rolling array — dp[j] = paths to reach column j in current row
// time = O(M*N), space = O(N)
public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[j] += dp[j-1];
    return dp[n-1];
}

2-6) Triangle (LC 120) — Top-Down Recursion → Bottom-Up DP

dp[i][j] = min path sum from (i,j) to bottom; convert triangle recursion bottom-up.

// LC 120 - Triangle
// IDEA: Bottom-up DP in-place — start from second-to-last row, accumulate minimum path
// time = O(N^2), space = O(1) modifying input
public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) dp[i] = triangle.get(n-1).get(i);
    for (int row = n-2; row >= 0; row--)
        for (int col = 0; col <= row; col++)
            dp[col] = triangle.get(row).get(col) + Math.min(dp[col], dp[col+1]);
    return dp[0];
}

2-7) Longest Palindromic Subsequence (LC 516) — Interval DP

dp[i][j] = LPS length in s[i…j]; recursion f(i,j) → bottom-up by increasing length.

// LC 516 - Longest Palindromic Subsequence
// IDEA: Interval DP — dp[i][j] = LPS in s[i..j]
// time = O(N^2), space = O(N^2)
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++)
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
            else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
    return dp[0][n-1];
}

2-8) Coin Change (LC 322) — Recursion with Pruning → DP

Recursion f(amount) = 1 + min(f(amount-coin)) → bottom-up unbounded knapsack DP.

// LC 322 - Coin Change
// IDEA: Bottom-up DP — dp[i] = min coins for amount i; unbounded knapsack
// time = O(amount * |coins|), space = O(amount)
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++)
        for (int coin : coins)
            if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

2-9) Combination Sum IV (LC 377) — Recursion → DP (Order Matters)

dp[i] = number of ordered combinations summing to i; unlike knapsack, order of adding matters.

// LC 377 - Combination Sum IV
// IDEA: DP — dp[i] = number of ordered ways to reach sum i
// time = O(target * |nums|), space = O(target)
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 1; i <= target; i++)
        for (int num : nums)
            if (num <= i) dp[i] += dp[i - num];
    return dp[target];
}

2-10) Minimum Cost to Cut a Stick (LC 1547) — Interval DP

dp[i][j] = min cost to make all cuts between cut[i] and cut[j]; try each middle cut.

// LC 1547 - Minimum Cost to Cut a Stick
// IDEA: Interval DP — insert endpoints; dp[i][j] = min cost for cuts between i and j
// time = O(M^3), space = O(M^2)  M = cuts.length
public int minCost(int n, int[] cuts) {
    int m = cuts.length;
    int[] c = new int[m + 2];
    c[0] = 0; c[m+1] = n;
    for (int i = 0; i < m; i++) c[i+1] = cuts[i];
    Arrays.sort(c);
    int[][] dp = new int[m+2][m+2];
    for (int len = 2; len <= m+1; len++)
        for (int i = 0; i + len <= m+1; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i+1; k < j; k++)
                dp[i][j] = Math.min(dp[i][j], c[j]-c[i] + dp[i][k] + dp[k][j]);
        }
    return dp[0][m+1];
}

2-11) Partition Array for Maximum Sum (LC 1043) — 1D DP

dp[i] = max sum of partitioning array up to index i; try all sub-partitions of size 1…k.

// LC 1043 - Partition Array for Maximum Sum
// IDEA: DP — dp[i] = max sum when array[0..i-1] is partitioned
// time = O(N * k), space = O(N)
public int maxSumAfterPartitioning(int[] arr, int k) {
    int n = arr.length;
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int maxVal = 0;
        for (int j = 1; j <= k && i - j >= 0; j++) {
            maxVal = Math.max(maxVal, arr[i-j]);
            dp[i] = Math.max(dp[i], dp[i-j] + maxVal * j);
        }
    }
    return dp[n];
}