Memoization

Uses recursion. Is our def dp(i) or def dp(i, j solution. This stores solutions to subproblems instead of repeating computations. Here, a hash table holds values.

An example of using memoization for the Knapsack problem

function knapsack(w̄)

if w̄ is in hashtable:
    return K(w̄) from hashtable

K(w̄) = max_{i : w_i ≤ w̄} { knapsack(w̄ - w_i) + v_i }

insert K(w̄) into hashtable with key w̄

return K(w̄)

Recursion is typically slower since it incurs overhead