Dynamic programming

Applies to: general, python

Dynamic programming solves a problem by combining answers to overlapping subproblems, computing each one once and reusing it. It applies when a problem has optimal substructure and repeated subproblems, such as shortest paths, edit distance, and counting problems.

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]   # fibonacci, bottom-up

See also: recursion, memoization