Dynamic Programming Cheat Sheet

Explains dynamic programming fundamentals, overlapping subproblems and optimal substructure, through memoization, tabulation, knapsack, and LCS examples.

2 PagesAdvancedApr 12, 2026

Core DP Concepts

The vocabulary behind every dynamic programming solution.

Overlapping Subproblems- The same smaller subproblems are solved repeatedly in a naive recursive solution — DP caches them
Optimal Substructure- An optimal solution can be built from optimal solutions to its subproblems
Memoization (top-down)- Recursion plus a cache (dict/array) storing results of subproblems the first time they're computed
Tabulation (bottom-up)- Iteratively fills a table from base cases up to the final answer, avoiding recursion overhead
State- The set of parameters that uniquely identify a subproblem, e.g. (index, remaining_capacity) in knapsack
Space optimization- Many DP tables only need the previous row or state, letting you reduce O(n*m) space down to O(m)

Top-Down Memoization

Turning exponential recursion into linear time.

python

def fib(n, memo={}):    if n in memo:        return memo[n]    if n <= 1:        return n    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)    return memo[n]fib(50)   # O(n) time instead of O(2^n) with naive recursion

Bottom-Up Tabulation: 0/1 Knapsack

Building a DP table iteratively.

python

def knapsack(weights, values, capacity):    n = len(weights)    dp = [[0] * (capacity + 1) for _ in range(n + 1)]    for i in range(1, n + 1):        for w in range(capacity + 1):            dp[i][w] = dp[i - 1][w]   # don't take item i-1            if weights[i - 1] <= w:                dp[i][w] = max(dp[i][w],                                dp[i - 1][w - weights[i - 1]] + values[i - 1])    return dp[n][capacity]knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)   # => 9

Longest Common Subsequence

A classic 2D DP problem over two sequences.

python

def lcs(a, b):    m, n = len(a), len(b)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(1, m + 1):        for j in range(1, n + 1):            if a[i - 1] == b[j - 1]:                dp[i][j] = dp[i - 1][j - 1] + 1            else:                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])    return dp[m][n]lcs("ABCBDAB", "BDCABA")   # => 4 ("BCBA")

Pro Tip

When converting a recursive solution to DP, first write the naive recursion and identify the state (its arguments) — if two different call paths ever produce the same arguments, you have overlapping subproblems and DP will help.

Was this cheat sheet helpful?

Searching Algorithms Cheat Sheet

Graph Algorithms Cheat Sheet

Explore Topics

#DynamicProgramming#DynamicProgrammingCheatSheet#Programming#Advanced#CoreDPConcepts#TopDownMemoization#BottomUpTabulation01Knapsack#LongestCommonSubsequence#CheatSheet#SkillVeris

Sri Hayavadhana Info-Tech

Professional Web Designing Services