Greedy vs DP How to Know Which to Apply in DSA C - 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, solving each once, and storing results to avoid repeated work.

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 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 tell if a problem needs DP instead of Greedy?

If the problem has overlapping subproblems and no greedy-choice property, DP is needed to explore all options and store results.

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

A Memoization

B Overlapping subproblems

C Greedy-choice property

D Backtracking

Greedy-choice property means local best choices lead to global best solution, essential for Greedy to work.

What does Dynamic Programming use to avoid repeated work?

A Memoization or tabulation

B Greedy choices

C Random guessing

D Divide and conquer without storage

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

If a problem has overlapping subproblems but also a greedy-choice property, which approach is better?

A Backtracking

B Greedy

C Brute force

D Dynamic Programming

Greedy is preferred if greedy-choice property holds, even if subproblems overlap.

Which of these problems is typically solved by Dynamic Programming?

A Fibonacci sequence calculation

B Finding minimum spanning tree

C Sorting an array

D Binary search

Fibonacci has overlapping subproblems and optimal substructure, ideal for DP.

What is NOT a sign that Greedy might fail?

A Local choices don't lead to global optimum

B Overlapping subproblems

C No greedy-choice property

D Optimal substructure

Optimal substructure alone does not mean Greedy fails; it is necessary but not sufficient.

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

Think about whether making the best choice now guarantees the best overall solution.

Describe the key differences between Greedy and Dynamic Programming approaches.

Consider how each approach handles problem parts and solution building.