1D Dynamic Programming
Overview
Dynamic Programming (DP) is a scary-sounding academic term for a remarkably simple, beautiful concept: Remembering past results so you don't have to recalculate them.
If you ask a naive recursive function to calculate Fibonacci(40), it will call fib(39) + fib(38). But fib(39) also branches out and calls fib(38). The function recalculates fib(38) twice, fib(37) three times, and fib(2) millions of times. The time complexity is a disastrous, exponential O(2^N).
1D DP introduces a 1-Dimensional Array to act as a Cache. When you calculate fib(38), you save the answer in cache[38]. The next time the algorithm needs fib(38), it skips the recursive branching entirely and just instantly returns the cached value in O(1) time. This simple trick drops the time complexity from an unrunnable O(2^N) down to a lightning-fast O(N).
Syntax
public class DynamicProgramming {
// Calculates the Nth Fibonacci number in O(N) time
public int fibonacci(int n) {
if (n <= 1) return n;
// The DP Cache Array
int[] dp = new int[n + 1];
// Base cases
dp[0] = 0;
dp[1] = 1;
// Iterate and calculate, relying exclusively on previously saved results
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}Common Pitfalls
- Array out of bounds for base cases. If
n=0, creatingdp = new int[n+1]creates an array of size 1. Trying to assigndp[1] = 1will crash with an IndexOutOfBoundsException. Always handle base casesif (n <= 1) return n;before initializing the array. - Not identifying overlapping subproblems. DP only works if the problem can be broken down into subproblems that repeat. If every subproblem is completely unique, caching doesn't help you.
- Integer Overflow. Problems like Fibonacci grow exponentially large in value.
fib(50)exceeds the maximum capacity of a 32-bit Javaint. Always uselong[]or BigInteger for DP problems dealing with large combinatorics.
Interview Questions
1. Overlapping Subproblems (the same smaller problems are solved repeatedly). 2. Optimal Substructure (the optimal solution to the main problem can be constructed from the optimal solutions of its subproblems).
It drops it from exponential O(2^N) down to linear O(N).
Real-World Example
Caching repeating pure functions in functional programming, or memoizing heavy API requests. If an expensive algorithm (like pricing a complex derivative in finance) is called with the exact same parameters multiple times a second, DP techniques cache the first result to instantly serve the subsequent identical requests.
public class PricingEngine {
// 1D DP Cache for pricing calculations
private Map<Integer, Double> pricingCache = new HashMap<>();
public double calculatePrice(int riskScore) {
// If we already did this heavy math, return it instantly
if (pricingCache.containsKey(riskScore)) {
return pricingCache.get(riskScore);
}
// Heavy, 5-second calculation
double price = performHeavyMonteCarloSimulation(riskScore);
// Save to cache before returning
pricingCache.put(riskScore, price);
return price;
}
}Check Your Knowledge
Test your understanding of 1D Dynamic Programming with these quick questions.