dynamic-programming

When to use

Use dynamic programming when a problem has overlapping subproblems (same computation repeated) and optimal substructure (optimal solution built from optimal sub-solutions).

Signs

"find minimum cost," "count the number of ways," "longest/shortest subsequence," "can you reach."

Rules

• Define state (what changes between subproblems) and recurrence (how states relate)
• Top-down with @cache is easiest to write; bottom-up tabulation avoids recursion limits and is often faster
• ALWAYS check if you can reduce space by keeping only the previous row/state instead of the full table
• NEVER memoize without verifying overlapping subproblems exist

Approach