1D Dynamic Programming — Complete Guide

What is 1D DP?

Dynamic programming solves problems by breaking them into overlapping subproblems and storing results. In 1D DP, the state space is a single array — dp[i] represents some optimal answer considering the first i items or ending at position i.

The 8 Core 1D DP Patterns

Pattern 1 — Fibonacci / Staircase

Current state depends on the previous 1 or 2 states.

dp[i] = dp[i-1] + dp[i-2]

Problems: Climbing Stairs, Fibonacci Number, Min Cost Climbing Stairs

Pattern 2 — House Robber (Skip 1)

Can't pick adjacent elements. Take vs skip.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Problems: House Robber, House Robber II, Delete & Earn

Pattern 3 — Kadane (Max Subarray)

Max subarray ending at index i: extend or restart.

dp[i] = max(nums[i], dp[i-1] + nums[i])

Problems: Max Subarray, Max Product Subarray

Pattern 4 — Coin Change (Unbounded Knapsack)

Minimum coins: try all denominations.

dp[amount] = min(dp[amount-coin]+1) for each coin

Problems: Coin Change, Coin Change II, Perfect Squares

Pattern 5 — LIS (Longest Increasing Subsequence)

O(n²) DP or O(n log n) patience sorting.

dp[i] = max(dp[j]+1) for j < i where nums[j] < nums[i]

Problems: LIS, Russian Dolls, Longest Bitonic Subseq

Pattern 6 — Jump Game

Can you reach / min jumps to reach end.

reach = max(reach, i + nums[i])

Problems: Jump Game, Jump Game II, Jump Game III

Pattern 7 — Decode Ways / Counting

Count ways to decode/partition with valid sub-choices.

dp[i] = dp[i-1] (single digit) + dp[i-2] (two digits if valid)

Problems: Decode Ways, Climbing Stairs with Constraints

Pattern 8 — Palindromic Subsequences

Count/find longest palindromic subsequence in 1D or 2D.

# For palindrome substrings, expand around center
# For palindromic subsequence, use 2D DP

Complexity Reference

5-Language Templates

Fibonacci (Space Optimized)

# Python
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a

// C++
int a=0, b=1;
for(int i=0;i<n;i++){int c=a+b;a=b;b=c;}
return a;

// Java
int a=0,b=1;
for(int i=0;i<n;i++){int c=a+b;a=b;b=c;}
return a;

// JavaScript
let [a,b]=[0,1];
for(let i=0;i<n;i++){[a,b]=[b,a+b];}
return a;

// C
int a=0,b=1,c;
for(int i=0;i<n;i++){c=a+b;a=b;b=c;}
return a;

Problem Index