DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Build Both Approaches

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: Imagine you are helping a delivery company decide the best way to pack boxes with items to maximize value without exceeding weight limits. You will explore three ways to solve this: simple recursion, greedy choice, and dynamic programming.

🎯 Goal: You will create a list of items with weights and values, set a maximum weight limit, then write code to find the best total value using recursion, greedy, and dynamic programming approaches. Finally, you will print the results to compare.

📋 What You'll Learn

Create a list of items with exact weights and values

Set a maximum weight limit variable

Write a recursive function to find max value without exceeding weight

Write a greedy function that picks items by value-to-weight ratio

Write a dynamic programming function to find max value efficiently

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Packing delivery boxes or loading cargo efficiently to maximize value without exceeding weight limits.

💼 Career

Understanding when to use recursion, greedy algorithms, or dynamic programming is key for software engineers solving optimization problems.

1

Create the list of items

Create a variable called items as an array of objects with these exact entries: { weight: 2, value: 3 }, { weight: 3, value: 4 }, { weight: 4, value: 5 }, and { weight: 5, value: 8 }.

DSA Typescript

// Your code here

Hint

Use const items = [ ... ] with objects inside.

2

Set the maximum weight limit

Create a variable called maxWeight and set it to 8.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];
// Your code here

Hint

Use const maxWeight = 8; to set the limit.

3

Write the recursive function to find max value

Write a function called knapsackRecursive that takes index and remainingWeight as parameters and returns the maximum value. Use recursion to decide whether to include or exclude the current item at items[index]. If index is out of range or remainingWeight is zero or less, return 0.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];

const maxWeight = 8;

// Your code here

Hint

Use recursion with base case when index is beyond last item or no weight left.

4

Print the results of all methods

Write three lines to print the results of calling knapsackRecursive(0, maxWeight), knapsackGreedy(), and knapsackDP(). Use console.log with labels: "Recursive:", "Greedy:", and "DP:" respectively.

DSA Typescript

const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 5 },
  { weight: 5, value: 8 }
];

const maxWeight = 8;

function knapsackRecursive(index: number, remainingWeight: number): number {
  if (index >= items.length || remainingWeight  remainingWeight) {
    return knapsackRecursive(index + 1, remainingWeight);
  } else {
    const include = items[index].value + knapsackRecursive(index + 1, remainingWeight - items[index].weight);
    const exclude = knapsackRecursive(index + 1, remainingWeight);
    return Math.max(include, exclude);
  }
}

function knapsackGreedy(): number {
  const sortedItems = [...items].sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let totalWeight = 0;
  let totalValue = 0;
  for (const item of sortedItems) {
    if (totalWeight + item.weight  Array(maxWeight + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= maxWeight; w++) {
      if (items[i - 1].weight <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - items[i - 1].weight] + items[i - 1].value);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][maxWeight];
}

// Your code here

Hint

Use console.log("Recursive:", knapsackRecursive(0, maxWeight)) and similar for greedy and DP.

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