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.