Dynamic Programming from Scratch (2026)
Dynamic Programming (DP) is an algorithmic technique for solving optimization problems by breaking them into overlapping subproblems and storing their solutions. Unlike divide and conquer, DP solves each subproblem only once and reuses the result. DP is applicable when a problem has optimal substructure (the optimal solution contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems are solved repeatedly).
In this tutorial, we will implement memoization (top-down) and tabulation (bottom-up) approaches, solve classic problems like 0/1 knapsack, Longest Common Subsequence (LCS), and Longest Increasing Subsequence (LIS), and learn to identify and solve DP problems systematically.
Memoization vs Tabulation
Memoization (top-down) uses recursion with a cache to store results of subproblems. When a subproblem is first solved, its result is cached; subsequent calls return the cached value. Tabulation (bottom-up) solves subproblems iteratively, filling a table from the smallest subproblems to the largest. Both approaches have the same time complexity but different space usage and constant factors.
Memoization is easier to implement when the recursion is natural and the subproblem graph is sparse. Tabulation is often more efficient due to no recursion overhead and better cache locality.
#include
#include
using namespace std;
long long fibMemo(int n, vector& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
return memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
}
long long fibTab(int n) {
if (n <= 1) return n;
vector dp(n+1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
long long fibOptimized(int n) {
if (n <= 1) return n;
long long p2 = 0, p1 = 1, curr;
for (int i = 2; i <= n; i++) {
curr = p1 + p2; p2 = p1; p1 = curr;
}
return curr;
}
int main() {
int n = 50;
vector memo(n+1, -1);
cout << "Memo: " << fibMemo(n, memo) << endl;
cout << "Tab: " << fibTab(n) << endl;
cout << "Opt: " << fibOptimized(n) << endl;
} 0/1 Knapsack Problem
The 0/1 knapsack problem: given items with weights and values, and a knapsack capacity, find the maximum value by selecting items where each item can be taken at most once. The DP approach defines dp[i][w] as the maximum value using items 1..i with capacity w. For each item, we either include it (if it fits) or exclude it, taking the maximum of both choices.
The recurrence is: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] <= w, else dp[i-1][w]. The time and space complexity are O(n * W).
def knapsack_01(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]
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]
def knapsack_01_optimized(weights, values, capacity):
dp = [0]*(capacity+1)
for i in range(len(weights)):
for w in range(capacity, weights[i]-1, -1):
dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
return dp[capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_01(weights, values, 8)) # 10
print(knapsack_01_optimized(weights, values, 8)) # 10Longest Common Subsequence (LCS)
LCS finds the longest subsequence common to two strings. A subsequence is a sequence that appears in the same order but not necessarily contiguously. The DP approach defines dp[i][j] as the LCS length of the first i characters of string1 and first j characters of string2. If characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
LCS has applications in diff tools, version control, bioinformatics (DNA sequence alignment), and spell checking. The time and space complexity are O(m*n).
public class LCS {
static int lcs(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}
static String lcsString(String s1, String s2) {
int m=s1.length(), n=s2.length();
int[][] dp = new int[m+1][n+1];
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)
if (s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
StringBuilder sb = new StringBuilder();
int i=m, j=n;
while (i>0 && j>0) {
if (s1.charAt(i-1)==s2.charAt(j-1)) { sb.append(s1.charAt(i-1)); i--; j--; }
else if (dp[i-1][j] > dp[i][j-1]) i--;
else j--;
}
return sb.reverse().toString();
}
}Longest Increasing Subsequence (LIS)
LIS finds the length of the longest subsequence where elements are in strictly increasing order. The O(n^2) DP approach defines dp[i] as the length of LIS ending at index i. For each element, we check all previous elements and extend the longest subsequence that ends with a smaller value. The answer is the maximum dp[i].
The O(n log n) approach uses binary search with a patience sorting technique. We maintain an array of the smallest tail of all increasing subsequences of length i+1. For each element, we use binary search to find where it should be placed.
import bisect
def lis_dp(arr):
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def lis_binary_search(arr):
tails = []
for num in arr:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
def lis_with_sequence(arr):
n = len(arr)
dp = [1] * n
parent = [-1] * n
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
parent[i] = j
max_len = max(dp)
idx = dp.index(max_len)
seq = []
while idx != -1:
seq.append(arr[idx])
idx = parent[idx]
return seq[::-1]
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_dp(arr)) # 4
print(lis_binary_search(arr)) # 4
print(lis_with_sequence(arr)) # [2, 3, 7, 18]Frequently Asked Questions
When to use memoization vs tabulation?
Memoization is easier when the recursion is natural and subproblems are sparse. Tabulation is more efficient (no recursion overhead, better cache locality) and can be space-optimized by only keeping necessary rows.
How to identify a DP problem?
Look for: (1) optimal substructure - optimal solution contains optimal sub-solutions, (2) overlapping subproblems - same subproblems solved repeatedly. If both exist, DP is applicable.
What is the 0/1 knapsack?
Given items with weights and values, and a capacity, maximize total value where each item can be taken at most once. Solved with DP in O(nW) time. Unlike fractional knapsack, greedy does not work.
What is LCS and LIS?
LCS (Longest Common Subsequence) finds the longest subsequence common to two strings in O(mn). LIS (Longest Increasing Subsequence) finds the longest strictly increasing subsequence in O(n log n) with binary search.
Originally published on Ayodhyyya. Last updated June 1, 2026.