dsa4 min read
1D Dynamic Programming — Complete Guide
Master 1D DP: Fibonacci/Climbing Stairs, House Robber, LIS, Coin Change, Jump Game, and Kadane patterns with 5-language templates.
Read →
1d-dp
23 articles
dsa1 min read
Climbing Stairs — Fibonacci DP
Count ways to climb n stairs taking 1 or 2 steps. Classic Fibonacci DP — dp[n] = dp[n-1] + dp[n-2] with O(1) space.
Read →
dsa1 min read
Min Cost Climbing Stairs — Fibonacci DP
Find minimum cost to reach the top of stairs. Each stair has a cost; you can take 1 or 2 steps. DP: min cost to reach each stair.
Read →
dsa1 min read
House Robber — Skip Adjacent DP
Maximize amount robbed without robbing adjacent houses. Classic skip-one DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Read →
dsa1 min read
House Robber II — Circular Array DP
Houses arranged in a circle: first and last are adjacent. Run linear House Robber twice: once excluding last house, once excluding first.
Read →
dsa1 min read
Delete and Earn — House Robber on Frequency Array
Picking value k deletes all k-1 and k+1 elements. Map to House Robber: earn[k] = k * count(k), then max non-adjacent sum.
Read →
dsa1 min read
Maximum Subarray — Kadane's Algorithm
Find the contiguous subarray with the largest sum. Kadane's algorithm: either extend previous subarray or start fresh at current element.
Read →
dsa1 min read
Maximum Product Subarray — Kadane with Min/Max
Find maximum product of a contiguous subarray. Track both min and max at each position because a negative * negative becomes positive.
Read →
dsa2 min read
Coin Change — Unbounded Knapsack DP
Find minimum coins to make amount. Unbounded knapsack DP: dp[amount] = min(dp[amount-coin]+1) over all coins. Bottom-up from 0 to amount.
Read →
dsa1 min read
Coin Change II — Count Ways Unbounded Knapsack
Count number of combinations making up amount. Process each coin denomination completely (outer loop = coin) to avoid counting permutations.
Read →
dsa1 min read
Perfect Squares — Coin Change with Squares
Minimum perfect squares summing to n. Isomorphic to Coin Change where coins = all perfect squares ≤ n.
Read →
dsa1 min read
Jump Game — Greedy Reachability
Check if you can reach the last index. Greedy: track furthest reachable index. If current position > reach, stuck.
Read →
dsa1 min read
Jump Game II — Minimum Jumps Greedy
Find minimum jumps to reach the last index. Greedy: at each jump boundary, extend to the farthest reachable position.
Read →
dsa1 min read
Decode Ways — Counting DP
Count ways to decode a digit string as letters (A=1,...,Z=26). DP: single digit + valid double digit transitions.
Read →
dsa1 min read
Word Break — Reachability DP
Check if string can be segmented into dictionary words. DP: dp[i]=true if some dp[j] is true and s[j:i] is in wordDict.
Read →
dsa2 min read
Longest Increasing Subsequence — O(n log n) Patience Sorting
Find the length of the longest strictly increasing subsequence. O(n²) DP or O(n log n) patience sorting with binary search.
Read →
dsa1 min read
Russian Doll Envelopes — 2D LIS
Maximum envelopes you can nest. Sort by width ascending and height descending, then LIS on heights. Descending heights prevents using same-width twice.
Read →
dsa1 min read
Palindromic Substrings — Expand Around Center
Count palindromic substrings. Expand around each center (n odd-length + n-1 even-length centers), count valid expansions.
Read →
dsa1 min read
Longest Palindromic Subsequence — 2D DP
Find longest palindromic subsequence length. 2D DP: if s[i]==s[j], dp[i][j] = dp[i+1][j-1]+2, else max of neighbors. Fill diagonally.
Read →
dsa2 min read
Partition Equal Subset Sum — 0/1 Knapsack
Can array be partitioned into two equal-sum subsets? 0/1 knapsack: can we pick some numbers summing to total/2? Bitset or DP boolean array.
Read →
dsa1 min read
Target Sum — DP Count Ways
Assign + or - to each number to reach target sum. DP counts ways to reach each sum. Reduces to 0/1 knapsack subset sum count.
Read →
dsa1 min read
Longest Common Subsequence — 2D DP Preview
LCS of two strings: dp[i][j] = LCS of first i chars of s1 and first j chars of s2. Full 2D DP treatment in the 2D DP section.
Read →
dsa2 min read
1D Dynamic Programming — Master Recap & Cheatsheet
Complete 1D DP cheatsheet: 8 patterns, key transitions, complexity table, and problem index.
Read →