Top DP Problems
In this page:
DP Idea
Dynamic programming's core idea is to store the answer to each distinct subproblem the first time it's solved, so any later request for that same subproblem returns instantly instead of being recomputed from scratch.
Example: DP Idea
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int,int> cache;
int fib(int n) {
if (n <= 1) return n;
if (cache.count(n)) return cache[n];
return cache[n] = fib(n-1) + fib(n-2);
}
int main() { cout << "Stored once, reused instantly on later requests: fib(15) = " << fib(15); return 0; }import java.util.*;
public class Main {
static Map<Integer,Integer> cache = new HashMap<>();
static int fib(int n) {
if (n <= 1) return n;
if (cache.containsKey(n)) return cache.get(n);
int r = fib(n-1) + fib(n-2);
cache.put(n, r);
return r;
}
public static void main(String[] args) { System.out.println("Stored once, reused instantly on later requests: fib(15) = " + fib(15)); }
}cache = {}
def fib(n):
if n <= 1:
return n
if n in cache:
return cache[n]
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
print("Stored once, reused instantly on later requests: fib(15) =", fib(15))#include <stdio.h>
int cache[16]={0}, computed[16]={0};
int fib(int n) {
if (n <= 1) return n;
if (computed[n]) return cache[n];
computed[n] = 1;
return cache[n] = fib(n-1) + fib(n-2);
}
int main() { printf("Stored once, reused instantly on later requests: fib(15) = %d", fib(15)); return 0; }Login to try C/C++/Java code in the editor
Fibonacci
Fibonacci is the simplest illustration of overlapping subproblems: naive recursion recomputes the same smaller Fibonacci values repeatedly, and storing each value the first time fixes that redundancy immediately.
Example: Fibonacci
#include <iostream>
using namespace std;
int main() {
int dp[11]; dp[0]=0; dp[1]=1;
for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
cout << "fib(10) = " << dp[10] << " built bottom-up, no recomputation";
return 0;
}public class Main {
public static void main(String[] args) {
int[] dp = new int[11]; dp[0]=0; dp[1]=1;
for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
System.out.println("fib(10) = " + dp[10] + " built bottom-up, no recomputation");
}
}dp = [0]*11
dp[1] = 1
for i in range(2, 11):
dp[i] = dp[i-1] + dp[i-2]
print("fib(10) =", dp[10], "built bottom-up, no recomputation")#include <stdio.h>
int main() {
int dp[11]; dp[0]=0; dp[1]=1;
for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
printf("fib(10) = %d built bottom-up, no recomputation", dp[10]);
return 0;
}Login to try C/C++/Java code in the editor
Climbing Stairs
The number of distinct ways to climb a staircase (taking 1 or 2 steps at a time) at step n is built directly from the number of ways to reach step n-1 and step n-2 — the exact same recurrence shape as Fibonacci, just framed differently.
Example: Climbing Stairs
#include <iostream>
using namespace std;
int main() {
int n = 5;
int dp[6]; dp[0]=1; dp[1]=1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
cout << "Ways to climb " << n << " stairs (1 or 2 at a time): " << dp[n];
return 0;
}public class Main {
public static void main(String[] args) {
int n = 5;
int[] dp = new int[6]; dp[0]=1; dp[1]=1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
System.out.println("Ways to climb " + n + " stairs (1 or 2 at a time): " + dp[n]);
}
}n = 5
dp = [0]*(n+1)
dp[0] = dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(f"Ways to climb {n} stairs (1 or 2 at a time): {dp[n]}")#include <stdio.h>
int main() {
int n = 5;
int dp[6]; dp[0]=1; dp[1]=1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
printf("Ways to climb %d stairs (1 or 2 at a time): %d", n, dp[n]);
return 0;
}Login to try C/C++/Java code in the editor
Knapsack
Knapsack-style DP problems choose a subset of items to maximize value while respecting a capacity constraint, deciding for each item whether including it is worth the value gained against the extra capacity it consumes.
Example: Knapsack
#include <iostream>
using namespace std;
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
int dp[6] = {0};
for (int i = 0; i < 3; i++)
for (int w = capacity; w >= weights[i]; w--)
dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
cout << "Best value under capacity " << capacity << ": " << dp[capacity];
return 0;
}public class Main {
public static void main(String[] args) {
int[] weights = {2,3,4}, values = {3,4,5};
int capacity = 5;
int[] dp = new int[6];
for (int i = 0; i < 3; i++)
for (int w = capacity; w >= weights[i]; w--)
dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
System.out.println("Best value under capacity " + capacity + ": " + dp[capacity]);
}
}weights, values, capacity = [2,3,4], [3,4,5], 5
dp = [0]*(capacity+1)
for i in range(3):
for w in range(capacity, weights[i]-1, -1):
dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
print("Best value under capacity", capacity, ":", dp[capacity])#include <stdio.h>
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
int dp[6] = {0};
for (int i = 0; i < 3; i++)
for (int w = capacity; w >= weights[i]; w--)
if (dp[w-weights[i]] + values[i] > dp[w]) dp[w] = dp[w-weights[i]] + values[i];
printf("Best value under capacity %d: %d", capacity, dp[capacity]);
return 0;
}Login to try C/C++/Java code in the editor
DP Practice
Before writing any DP code, it helps to explicitly answer four questions: what does a state represent, how does a larger state get built from smaller ones, what are the base cases, and where does the final answer come from in the table.
Example: DP Practice
#include <iostream>
using namespace std;
int main() {
cout << "4 questions: what is a state, how is it built from smaller states, base cases, iteration order";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("4 questions: what is a state, how is it built from smaller states, base cases, iteration order");
}
}print("4 questions: what is a state, how is it built from smaller states, base cases, iteration order")#include <stdio.h>
int main() {
printf("4 questions: what is a state, how is it built from smaller states, base cases, iteration order");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 4 topics to unlock
0/4 topics done
Complete these topics first: