Dynamic Programming
Solve problems by combining solutions to overlapping sub-problems, storing each result once.
Advanced
DP applies when a problem has optimal substructure and overlapping sub-problems. Two styles:
- Memoisation (top-down): recursion + cache.
- Tabulation (bottom-up): fill a table iteratively.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2) # O(n) instead of O(2^n)
Classic problems: knapsack, longest common subsequence, edit distance, coin change and shortest paths (Bellman-Ford, Floyd-Warshall).
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.