Dynamic Programming (1D)
Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing results to avoid redundant computation. 1D DP uses a single array (or a few variables) to store subproblem results, where each state depends on a fixed number of previous states. This covers problems like climbing stairs, house robber, coin change, and longest increasing subsequence.
When to Use
- →The problem has optimal substructure (optimal solution built from optimal sub-solutions)
- →The problem has overlapping subproblems (same subproblem solved multiple times)
- →You need to count the number of ways to reach a target
- →You need to find the minimum/maximum cost, length, or count along a linear sequence
- →A recursive solution has exponential time due to repeated work
Approach
Start by defining the state: what does dp[i] represent? For climbing stairs, dp[i] = number of ways to reach step i. For coin change, dp[i] = minimum coins to make amount i. For longest increasing subsequence, dp[i] = length of LIS ending at index i.
Next, write the recurrence relation. For climbing stairs: dp[i] = dp[i-1] + dp[i-2]. For coin change: dp[i] = min(dp[i - coin] + 1) for each coin. Identify the base cases (dp[0], dp[1], etc.).
Often you can optimize space from O(n) to O(1) by noting that each state depends on only a constant number of previous states. For house robber, you only need the previous two values, so two variables suffice instead of an array.
Code Template
// Climbing stairs (Fibonacci pattern)
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Coin change (minimize)
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Longest increasing subsequence
function lengthOfLIS(nums) {
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}