Topic 73 of 78
1D Dynamic Programming
Overview
Dynamic Programming (DP) is a technique for solving complex problems by breaking them down into simpler subproblems and storing the results of those subproblems so they never have to be computed again. 1D DP uses a single 1D array to store state. The classic example is the Fibonacci sequence or the Climbing Stairs problem, where the solution to step N relies solely on the solutions to steps N-1 and N-2.
Syntax
By storing the answers in the `dp` array, we avoid massive recursive recalculations, turning an O(2^N) algorithm into an O(N) algorithm.
Fibonacci sequence
java
// You can climb 1 or 2 steps at a time. How many ways to reach top?
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1; // 1 way to reach step 1
dp[2] = 2; // 2 ways to reach step 2
// Build from the bottom up
for (int i = 3; i <= n; i++) {
// The ways to get to step 'i' is the sum of ways to get to 'i-1' and 'i-2'
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Common Pitfalls
- Overcomplicating the state transition formula. Always try to write down the mathematical relationship on paper first (e.g., `dp[i] = max(dp[i-1], dp[i-2] + current)`).
Interview Tips
- DP is simply Recursion + Caching.
Real-World Example
Calculating maximum continuous profit from an array of stock prices, or predicting population growth models.
example
java
// Space optimized Climbing Stairs O(1) Space
int a = 1, b = 2, c = 0;
for(int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;