Greedy vs DP How to Know Which to Apply in DSA Typescript - Key Differences

Recall & Review

beginner

What is the main idea behind the Greedy approach?

Greedy approach makes the best choice at each step, hoping to find the overall best solution without reconsidering previous choices.

beginner

What does Dynamic Programming (DP) do differently from Greedy?

DP solves problems by breaking them into smaller overlapping subproblems and storing their results to avoid repeated work, ensuring an optimal solution.

intermediate

When should you use Greedy over DP?

Use Greedy when the problem has the greedy-choice property and optimal substructure, meaning local best choices lead to a global best solution.

beginner

What is the 'optimal substructure' property?

A problem has optimal substructure if an optimal solution can be built from optimal solutions of its subproblems.

intermediate

How can you check if a problem requires DP instead of Greedy?

If making a local best choice doesn't guarantee a global best solution or subproblems overlap, DP is needed to explore all possibilities and store results.

Which property must a problem have for Greedy to work correctly?

A Greedy-choice property

B Overlapping subproblems

C Memoization

D Backtracking

Greedy works when the problem has the greedy-choice property, meaning local choices lead to a global optimum.

What does Dynamic Programming use to avoid repeated work?

A Memoization or tabulation

B Random guessing

C Greedy choices

D Divide and conquer without storing results

DP stores results of subproblems using memoization or tabulation to avoid recalculating them.

If a problem's local best choice does NOT guarantee a global best solution, which approach is better?

A Greedy

B Brute force only

C Dynamic Programming

D No solution

DP explores all subproblems and stores results to find the global best solution when greedy fails.

Which of these is NOT a sign that DP might be needed?

A Need to store intermediate results

B Optimal substructure

C Overlapping subproblems

D Greedy-choice property

Greedy-choice property suggests greedy approach, not DP.

What is a quick way to test if Greedy works for a problem?

A Use brute force

B Try local best choices and check if global solution is optimal

C Always use DP first

D Ignore subproblems

Testing if local best choices lead to global optimum helps decide if greedy works.

Explain how to decide between using Greedy or Dynamic Programming for a problem.

Think about whether local best choices always lead to the best overall solution.

Describe the key differences between Greedy and Dynamic Programming approaches.

Focus on how each method approaches problem solving step-by-step.

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