Greedy vs DP How to Know Which to Apply in DSA Typescript - Visual Comparison

Concept Flow - Greedy vs DP How to Know Which to Apply

Start Problem

↓

Check if problem has optimal substructure?

Yes↓

Check if problem has overlapping subproblems?

Yes No↓

Use DP

↓

Solve Problem

↓

End

Decide by checking if the problem has optimal substructure and overlapping subproblems. Use DP if both exist, else greedy.

Execution Sample

DSA Typescript

function chooseApproach(problem) {
  if (!problem.hasOptimalSubstructure) return 'No solution';
  if (problem.hasOverlappingSubproblems) return 'Use DP';
  return 'Use Greedy';
}

This code decides whether to use DP or Greedy based on problem properties.

Execution Table

Step	Check	Condition	Decision	Reasoning
1	Check optimal substructure	Yes	Continue	Problem can be broken into subproblems with optimal solutions
2	Check overlapping subproblems	Yes	Use DP	Subproblems repeat, so store results to avoid recomputation
3	Decision	-	DP chosen	Because both conditions met
4	End	-	-	Problem solved using DP

💡 Decision made based on problem properties: optimal substructure and overlapping subproblems

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
hasOptimalSubstructure	unknown	true	true	true
hasOverlappingSubproblems	unknown	unknown	true	true
decision	none	none	DP	DP

Key Moments - 3 Insights

Why do we check for optimal substructure first?

Because without optimal substructure, neither greedy nor DP can guarantee correct solutions. See execution_table step 1.

What if the problem has optimal substructure but no overlapping subproblems?

Then greedy approach is preferred since DP's memoization is unnecessary. This is shown in concept_flow where 'No' leads to greedy.

Why is overlapping subproblems important for DP?

Because DP saves time by storing results of repeated subproblems. Without overlap, DP adds overhead. See execution_table step 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the decision at step 2?

A Use DP

B Use Greedy

C No solution

D Continue checking

💡 Hint

Check the 'Decision' column at step 2 in execution_table

At which step does the code decide to use DP?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Decision' and 'Reasoning' columns in execution_table rows

If the problem has no overlapping subproblems, which approach is chosen according to concept_flow?

A DP

B No solution

C Greedy

D Brute force

💡 Hint

See the branch in concept_flow after checking overlapping subproblems

Concept Snapshot

Greedy vs DP decision:
1. Check optimal substructure: problem can be split into optimal subproblems.
2. Check overlapping subproblems: repeated subproblems exist.
3. If both yes, use DP (store results).
4. If no overlap, use Greedy (make local best choices).
5. If no optimal substructure, no efficient solution guaranteed.

Full Transcript

To decide between Greedy and Dynamic Programming (DP), first check if the problem has optimal substructure, meaning the problem can be broken into smaller subproblems whose optimal solutions combine to solve the bigger problem. If this is false, neither approach works well. Next, check if the problem has overlapping subproblems, meaning the same subproblems appear multiple times. If yes, DP is preferred because it stores results to avoid repeated work. If no overlapping subproblems, greedy approach is better as it makes local optimal choices without extra storage. This decision flow helps pick the right method for efficient problem solving.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem has the greedy choice property and optimal substructure

B. When the problem requires checking all possible combinations

C. When the problem has overlapping subproblems but no optimal substructure

D. When the problem needs to store all intermediate results

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum.

2. Step 2: Check optimal substructure

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

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option A

4. Quick Check:

   Greedy = greedy choice + optimal substructure [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Ignoring optimal substructure requirement

2. Which syntax correctly declares a memoization object in TypeScript for dynamic programming?

easy

A. var memo: number[] = [];

B. let memo = new Map();

C. const memo: Record = {};

D. const memo = {} as number[];

Solution

1. Step 1: Understand memo type for DP

   Memoization stores results with keys, so Record is suitable.

2. Step 2: Check syntax correctness

   const memo: Record = {}; correctly declares an empty object with number keys and values.

3. Final Answer:

   const memo: Record = {}; -> Option C

4. Quick Check:

   Memo object uses Record type [OK]

Hint: Use Record for memo objects [OK]

Common Mistakes:

• Using var instead of const or let
• Incorrect type assertion for memo
• Using Map without type parameters

3. Consider this TypeScript code snippet for a problem that can be solved by greedy or DP:

function maxSum(arr: number[]): number {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) sum += arr[i];
  }
  return sum;
}
console.log(maxSum([-1, 2, 3, -5, 4]));

What is the output?

medium

A. 9

B. 4

C. 0

D. Error

Solution

1. Step 1: Trace the loop and sum positive numbers

   Positive numbers are 2, 3, and 4. Sum = 2 + 3 + 4 = 9.

2. Step 2: Confirm return value

   The function returns sum = 9, so console.log prints 9.

3. Final Answer:

   9 -> Option A

4. Quick Check:

   Sum positives = 9 [OK]

Hint: Sum only positive numbers for max sum greedy [OK]

Common Mistakes:

• Adding negative numbers mistakenly
• Returning zero instead of sum
• Confusing output with array length

4. The following TypeScript function is intended to solve the Fibonacci sequence using DP with memoization. What is the bug?

function fib(n: number, memo: Record = {}): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. The recursive calls should be fib(n + 1) and fib(n + 2)

B. The base case should be 'if (n < 0) return 0;'

C. The function should not use default parameter for memo

D. The memo check should be 'if (memo[n] !== undefined)' to handle zero

Solution

1. Step 1: Analyze memo check condition

   Checking 'if (memo[n])' fails when memo[n] is 0, which is falsy.

2. Step 2: Correct memo check

   Use 'if (memo[n] !== undefined)' to correctly detect stored values including zero.

3. Final Answer:

   The memo check should be 'if (memo[n] !== undefined)' to handle zero -> Option D

4. Quick Check:

   Memo check must handle zero values [OK]

Hint: Check memo with !== undefined, not truthy check [OK]

Common Mistakes:

• Using truthy check for memo causing wrong cache hits
• Wrong base case for Fibonacci
• Incorrect recursive call directions

5. You have a set of tasks with durations and deadlines. You want to maximize the number of tasks completed before their deadlines. Which approach is best and why?

interface Task {
  duration: number;
  deadline: number;
}
function scheduleTasks(tasks: Task[]): number {
  // Implementation needed
}

hard

A. Use dynamic programming to try all subsets and pick max count

B. Use a greedy algorithm sorting tasks by earliest deadline to maximize count

C. Use greedy sorting by longest duration first to minimize total time

D. Use dynamic programming to minimize total duration ignoring deadlines

Solution

1. Step 1: Understand problem goal

   Maximize number of tasks completed before deadlines means scheduling tasks efficiently.

2. Step 2: Identify best approach

   Greedy algorithm sorting by earliest deadline ensures maximum tasks fit before deadlines.

3. Final Answer:

   Use a greedy algorithm sorting tasks by earliest deadline to maximize count -> Option B

4. Quick Check:

   Earliest deadline first greedy maximizes tasks [OK]

Hint: Sort tasks by earliest deadline for max count [OK]

Common Mistakes:

• Trying all subsets with DP causing inefficiency
• Sorting by longest duration wastes time
• Ignoring deadlines in scheduling