Keywords
Look for words like "Minimum", "Maximum", "Largest", "Smallest", "Longest", "Number of Ways", or "Is it possible". These are huge DP giveaways.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
Learn how to read a problem description and instantly recognize whether it requires Dynamic Programming, and if so, which pattern to apply.
Look for words like "Minimum", "Maximum", "Largest", "Smallest", "Longest", "Number of Ways", or "Is it possible". These are huge DP giveaways.
If N is ~10-20, it might be Backtracking or Bitmask DP. If N is ~100-500, it's likely O(N²) or O(N³) DP. If N is ~10^5, it must be O(N) linear DP or O(N log N).
Every DP problem boils down to three things: 1. Objective function (What to maximize?), 2. Base cases, 3. Transition function (How do states connect?).
Greedy makes the best local choice right now and never looks back. DP makes choices, but keeps all options open (memoized) because a bad local choice might lead to a great global choice later.