Which two properties indicate a problem fits dynamic programming?
Options
- Sorted input and unique values
- Overlapping subproblems and optimal substructure (Correct option)
- Graph input and the presence of cycles
- Recursion and some randomness in the choices
Answer
Overlapping subproblems and optimal substructure
Why
Dynamic programming (DP) solves a big problem by combining answers to smaller versions of it, and saves each small answer so it is computed only once.
It fits when:
- Optimal substructure: the best answer is built from best answers of subproblems.
- Overlapping subproblems: the same subproblems come up again and again.
Two styles: top-down with memoization (@lru_cache) or bottom-up filling a table.
Remember
DP = solve subproblems once and reuse them.