#
Problem
Difficulty
Status
Dynamic Programming breaks complex problems into overlapping subproblems, storing solutions to avoid redundant computation. Master the art of identifying optimal substructure and building solutions from smaller pieces.
An optimal solution contains optimal solutions to its subproblems. Like finding the best route: the best path from A to C through B uses the best path from A to B.
The same subproblems recur multiple times. Instead of recomputing, we store results (memoization) or build bottom-up (tabulation).
Define how to compute the current state from previous states. This recurrence relation is the heart of any DP solution.
Start from the main problem, recursively solve subproblems, and cache results.
def fib(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib(n-1) + fib(n-2)
return memo[n]Solve smallest subproblems first, build up to the main problem iteratively.
def fib(n):
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]