DP Introduction and Memoization
In this page:
DP Idea
Dynamic programming solves a problem by breaking it into smaller subproblems, but its real power comes from noticing that the same subproblem often gets solved repeatedly — DP simply solves each unique subproblem once and reuses the stored answer every other time it's needed.
Example: DP Idea
#include <iostream>
using namespace std;
int main() {
cout << "DP: break into subproblems, solve each unique one once, reuse the stored answer";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("DP: break into subproblems, solve each unique one once, reuse the stored answer");
}
}print("DP: break into subproblems, solve each unique one once, reuse the stored answer")#include <stdio.h>
int main() {
printf("DP: break into subproblems, solve each unique one once, reuse the stored answer");
return 0;
}Login to try C/C++/Java code in the editor
Memoization
Memoization is the top-down flavor of DP: you write the natural recursive solution, but before doing any work you check a cache to see whether this exact call has already been answered, and only compute it if it hasn't.
Example: Memoization
#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 << "fib(10) = " << fib(10) << " (cache checked before recomputing)";
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 result = fib(n-1) + fib(n-2);
cache.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println("fib(10) = " + fib(10) + " (cache checked before recomputing)");
}
}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(f"fib(10) = {fib(10)} (cache checked before recomputing)")#include <stdio.h>
int cache[11] = {0}; int computed[11] = {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("fib(10) = %d (cache checked before recomputing)", fib(10));
return 0;
}Login to try C/C++/Java code in the editor
Overlapping Subproblems
A problem has overlapping subproblems when a naive recursive solution ends up calling itself with identical arguments many times — plain recursive Fibonacci, for example, recomputes fib(2) exponentially many times as n grows.
Example: Overlapping Subproblems
#include <iostream>
using namespace std;
int calls = 0;
int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
int main() {
fib(10);
cout << "Naive fib(10) makes " << calls << " calls -- fib(2) alone gets recomputed dozens of times";
return 0;
}public class Main {
static int calls = 0;
static int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
fib(10);
System.out.println("Naive fib(10) makes " + calls + " calls -- fib(2) alone gets recomputed dozens of times");
}
}calls = 0
def fib(n):
global calls
calls += 1
if n <= 1:
return n
return fib(n-1) + fib(n-2)
fib(10)
print(f"Naive fib(10) makes {calls} calls -- fib(2) alone gets recomputed dozens of times")#include <stdio.h>
int calls = 0;
int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
int main() {
fib(10);
printf("Naive fib(10) makes %d calls -- fib(2) alone gets recomputed dozens of times", calls);
return 0;
}Login to try C/C++/Java code in the editor
Optimal Substructure
A problem has optimal substructure when the best answer to the whole problem can be assembled directly from the best answers to its smaller pieces, without needing to reconsider choices already made — this is what makes 'store and reuse' actually produce a correct final answer.
Example: Optimal Substructure
#include <iostream>
using namespace std;
int main() {
int best3 = 7, best4 = best3 + 2;
cout << "Best answer for size 4 (" << best4 << ") built directly from best answer for size 3 (" << best3 << ")";
return 0;
}public class Main {
public static void main(String[] args) {
int best3 = 7, best4 = best3 + 2;
System.out.println("Best answer for size 4 (" + best4 + ") built directly from best answer for size 3 (" + best3 + ")");
}
}best3 = 7
best4 = best3 + 2
print(f"Best answer for size 4 ({best4}) built directly from best answer for size 3 ({best3})")#include <stdio.h>
int main() {
int best3 = 7, best4 = best3 + 2;
printf("Best answer for size 4 (%d) built directly from best answer for size 3 (%d)", best4, best3);
return 0;
}Login to try C/C++/Java code in the editor
DP Practice
A good way to start any new DP problem is to define what a small state means in plain words, work out how a bigger state can be built from smaller ones, and only then translate that into code.
Example: DP Practice
#include <iostream>
using namespace std;
int main() {
cout << "Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code");
}
}print("Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code")#include <stdio.h>
int main() {
printf("Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: