DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Trade-offs & Analysis

Mental Model

We solve problems by breaking them down into smaller parts. Recursion tries all ways, greedy picks the best now, and DP remembers past results to avoid repeats.

Analogy: Imagine climbing stairs: recursion tries every path, greedy picks the next step that looks easiest, and DP remembers which steps are best to avoid climbing the same stairs again.

Recursion Tree:
    root
   /    \
  ...    ...

Greedy Path:
start -> best step -> next best -> ... -> end

DP Table:
Index: 0 1 2 3 4
Value: x x x x x
Memo:  x x x x x

Dry Run Walkthrough

Input: Problem: Find minimum cost to climb stairs with costs [10, 15, 20]

Goal: Compare how recursion, greedy, and DP solve this problem

Step 1: Recursion tries climbing from step 0: cost 10 + recurse from step 1

Recursion tree starts at step 0
Costs: 10 + ?

Why: Recursion explores all paths to find minimum cost

Step 2: Recursion tries climbing from step 1: cost 15 + recurse from step 2

Recursion tree at step 1
Costs: 15 + ?

Why: Recursion continues exploring all options

Step 3: Recursion tries climbing from step 2: cost 20 + recurse from step 3 (end)

Recursion tree at step 2
Costs: 20 + 0

Why: Reached end, base case returns 0

Step 4: Greedy picks step 0 cost 10, then step 1 cost 15, then step 2 cost 20, total 45

Greedy path: 10 -> 15 -> 20 = 45

Why: Greedy picks the cheapest immediate step

Step 5: DP fills memo: cost at step 2 is 20, step 1 is min(15+0, 15+20)=15, step 0 is min(10+15, 10+20)=25

DP memo: [25, 15, 20]

Why: DP remembers best cost from each step to avoid repeats

Step 6: DP returns minimum cost 25 starting from step 0

Final answer: 25

Why: DP finds optimal solution efficiently

Result:

DP memo: [25, 15, 20]
Minimum cost to climb stairs: 25

Annotated Code

DSA Typescript

class StairClimber {
  costs: number[];
  memo: number[];

  constructor(costs: number[]) {
    this.costs = costs;
    this.memo = Array(costs.length).fill(-1);
  }

  // Recursion: tries all paths
  minCostRecursion(step: number): number {
    if (step >= this.costs.length) return 0; // base case
    const costOneStep = this.costs[step] + this.minCostRecursion(step + 1); // step 1
    const costTwoSteps = this.costs[step] + this.minCostRecursion(step + 2); // step 2
    return Math.min(costOneStep, costTwoSteps);
  }

  // Greedy: picks cheapest immediate step
  minCostGreedy(): number {
    let total = 0;
    let i = 0;
    while (i < this.costs.length) {
      total += this.costs[i];
      if (i + 1 < this.costs.length && this.costs[i + 1] < (this.costs[i + 2] || Infinity)) {
        i += 1;
      } else {
        i += 2;
      }
    }
    return total;
  }

  // DP: remembers best cost from each step
  minCostDP(step: number): number {
    if (step >= this.costs.length) return 0; // base case
    if (this.memo[step] !== -1) return this.memo[step]; // return cached
    const costOneStep = this.costs[step] + this.minCostDP(step + 1);
    const costTwoSteps = this.costs[step] + this.minCostDP(step + 2);
    this.memo[step] = Math.min(costOneStep, costTwoSteps);
    return this.memo[step];
  }
}

// Driver code
const costs = [10, 15, 20];
const climber = new StairClimber(costs);
console.log("Recursion minimum cost:", climber.minCostRecursion(0));
console.log("Greedy minimum cost:", climber.minCostGreedy());
console.log("DP minimum cost:", climber.minCostDP(0));

if (step >= this.costs.length) return 0; // base case

stop recursion when past last step

const costOneStep = this.costs[step] + this.minCostRecursion(step + 1);

try taking one step forward

const costTwoSteps = this.costs[step] + this.minCostRecursion(step + 2);

try taking two steps forward

return Math.min(costOneStep, costTwoSteps);

choose cheaper path

while (i < this.costs.length) { total += this.costs[i]; ... }

sum costs by greedy choice

if (i + 1 < this.costs.length && this.costs[i + 1] < (this.costs[i + 2] || Infinity)) { i += 1; } else { i += 2; }

pick next step with smaller cost

if (this.memo[step] !== -1) return this.memo[step];

return cached result to avoid recomputation

this.memo[step] = Math.min(costOneStep, costTwoSteps);

store best cost for current step

Output

Recursion minimum cost: 25

Greedy minimum cost: 45

DP minimum cost: 25

Complexity Analysis

Time: Recursion: O(2^n) because it tries all paths; Greedy: O(n) because it picks steps once; DP: O(n) because it computes each step once and reuses results

Space: Recursion: O(n) due to call stack; Greedy: O(1) constant space; DP: O(n) for memo array

vs Alternative: DP is better than recursion because it avoids repeated work; greedy is fastest but can give wrong answers if problem needs global view

Edge Cases

Empty cost array

All methods return 0 cost

DSA Typescript

if (step >= this.costs.length) return 0; // base case

Single step cost array

Methods return cost of that single step

DSA Typescript

if (step >= this.costs.length) return 0; // base case

Costs with equal values

DP and recursion find correct minimum; greedy may pick suboptimal path

DSA Typescript

return Math.min(costOneStep, costTwoSteps);

When to Use This Pattern

When a problem asks for an optimal solution with overlapping subproblems, consider DP; if it can be solved by making local best choices, try greedy; if unsure, recursion helps explore all options.

Common Mistakes

Mistake: Using greedy when problem requires global optimization, leading to wrong answers
Fix: Check if problem has overlapping subproblems and optimal substructure; if yes, use DP

Mistake: Not caching results in recursion causing exponential time
Fix: Add memoization to store and reuse results

Summary

Recursion tries all possibilities, greedy picks local best, and DP remembers past results to avoid repeats.

Use recursion to explore, greedy when local choices guarantee global best, and DP when subproblems overlap.

The key is recognizing if the problem has overlapping subproblems and optimal substructure to pick DP over greedy or recursion.

Practice

1. Which approach is best when a problem can be broken into overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand overlapping subproblems

   Dynamic Programming works well when subproblems repeat and can be reused.

2. Step 2: Check optimal substructure property

   Dynamic Programming uses optimal solutions of subproblems to build the final solution.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memoization causing slow code
• Confusing brute force with DP

2. Which of the following TypeScript function signatures correctly implements a recursive Fibonacci function?

easy

A. function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); }

B. function fib(n: number): number { let a = 0; let b = 1; for(let i=2; i<=n; i++) { let c = a + b; a = b; b = c; } return b; }

C. function fib(n: number): number { return n + fib(n-1); }

D. function fib(n: number): number { if(n == 0) return 0; else return fib(n-1) * fib(n-2); }

Solution

1. Step 1: Check base case correctness

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } returns n if n <= 1, which correctly handles fib(0)=0 and fib(1)=1.

2. Step 2: Check recursive calls

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } calls fib(n-1) + fib(n-2), matching Fibonacci definition.

3. Final Answer:

   function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } -> Option A

4. Quick Check:

   Correct base case and recursive sum = function fib(n: number): number { return n <= 1 ? n : fib(n-1) + fib(n-2); } [OK]

Hint: Base case n<=1 and sum of fib(n-1)+fib(n-2) is key [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using multiplication instead of addition
• Incorrect loop instead of recursion

3. What is the output of the following TypeScript code using recursion to calculate factorial?

function factorial(n: number): number {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 10

B. Error

C. 120

D. 24

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3), factorial(3) = 3 * factorial(2), factorial(2) = 2 * factorial(1), factorial(1) = 1 * factorial(0), factorial(0) = 1.

2. Step 2: Calculate values bottom-up

   factorial(0) = 1, factorial(1) = 1*1=1, factorial(2) = 2*1=2, factorial(3) = 3*2=6, factorial(4) = 4*6=24.

3. Final Answer:

   24 -> Option D

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n*(n-1)! with base 0! = 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Missing base case causing stack overflow
• Incorrect multiplication order

4. The following greedy algorithm tries to find the minimum number of coins for a given amount. What is the bug?

function minCoins(coins: number[], amount: number): number {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (let coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
console.log(minCoins([1, 3, 4], 6));

medium

A. Sorting coins ascending instead of descending

B. Greedy fails for coin sets where local choice isn't optimal

C. Using floor division instead of ceil

D. Not handling zero amount input

Solution

1. Step 1: Understand greedy approach for coin change

   Greedy picks largest coin first, but it may not yield minimum coins for all coin sets.

2. Step 2: Check example with coins [1,3,4] and amount 6

   Greedy picks 4 once, then 1 twice = 3 coins; but optimal is 3+3 = 2 coins.

3. Final Answer:

   Greedy fails for coin sets where local choice isn't optimal -> Option B

4. Quick Check:

   Greedy not always optimal for coin change [OK]

Hint: Greedy fails if local best choice isn't globally best [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring coin sorting order
• Confusing floor and ceil division

5. You want to find the longest increasing subsequence (LIS) in an array. Which approach is best and why?
const arr = [10, 9, 2, 5, 3, 7, 101, 18];

hard

A. Greedy, because picking local max always gives LIS

B. Recursion without memoization, to explore all subsequences

C. Dynamic Programming, to store LIS lengths and build solution efficiently

D. Brute force, checking all subsequences

Solution

1. Step 1: Analyze problem characteristics

   LIS requires checking many subsequences with overlapping subproblems and optimal substructure.

2. Step 2: Choose approach with efficiency

   Dynamic Programming stores LIS lengths for subproblems, avoiding repeated work and improving speed.

3. Final Answer:

   Dynamic Programming, to store LIS lengths and build solution efficiently -> Option C

4. Quick Check:

   LIS best solved by DP due to overlapping subproblems [OK]

Hint: Use DP for LIS to avoid exponential recursion [OK]

Common Mistakes:

• Using greedy which fails for LIS
• Recursion without memoization causing slow code
• Trying brute force which is inefficient