DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Key Differences

Recall & Review

beginner

What is recursion in problem solving?

Recursion is a method where a function calls itself to solve smaller parts of a problem until it reaches a simple base case.

intermediate

What does DP (Dynamic Programming) do differently from simple recursion?

DP stores results of solved subproblems to avoid repeating work, making it faster than simple recursion for problems with overlapping subproblems.

beginner

When is a greedy algorithm the right choice?

A greedy algorithm works best when making the best local choice at each step leads to the best overall solution, without needing to reconsider previous choices.

intermediate

What kind of problems are best solved by DP rather than greedy?

Problems with overlapping subproblems and optimal substructure, where local choices alone don’t guarantee the best global solution, are best solved by DP.

intermediate

How can you decide between recursion, DP, and greedy for a new problem?

Check if the problem has overlapping subproblems and optimal substructure (use DP), if local best choices lead to global best (use greedy), or if it’s simple and small (recursion may be enough).

Which approach stores results to avoid repeated work?

A Brute Force

B Simple Recursion

C Dynamic Programming

D Greedy Algorithm

Dynamic Programming saves results of subproblems to avoid recalculating them.

When is a greedy algorithm NOT suitable?

A When problem has no overlapping subproblems

B When local choices don’t guarantee global best

C When problem is very small

D When recursion is easy to implement

Greedy fails if local best choices don’t lead to the best overall solution.

What is a base case in recursion?

A The simplest case that stops recursion

B The largest input size

C A repeated subproblem

D A greedy choice

Base case stops recursion by providing a direct answer.

Which property means a problem can be broken into smaller similar problems?

A Base case

B Greedy choice property

C Recursion depth

D Optimal substructure

Optimal substructure means the best solution can be built from best solutions of subproblems.

What is overlapping subproblems in DP?

A When the same subproblems appear multiple times

B When subproblems are all different

C When greedy choices overlap

D When recursion never ends

Overlapping subproblems means the same smaller problems repeat, so storing results helps.

Explain how to choose between recursion, dynamic programming, and greedy algorithms for solving a problem.

Think about problem structure and if repeated work happens.

Describe the main difference between dynamic programming and greedy algorithms.

Focus on how each approach makes decisions.

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