dsa4 min read
2D Dynamic Programming — Complete Guide
Master 2D DP: LCS, Edit Distance, grid path counting, matrix chain, interval DP, and stock patterns with 5-language templates.
Read →
2d-dp
23 articles
dsa1 min read
Unique Paths — Grid Path Count DP
Count paths from top-left to bottom-right moving only right or down. dp[i][j] = dp[i-1][j] + dp[i][j-1]. Math formula O(1) also works.
Read →
dsa1 min read
Unique Paths II — Grid with Obstacles
Count paths avoiding obstacle cells. Same DP but obstacles block cell (dp[i][j]=0) and obstacle at start/end returns 0.
Read →
dsa1 min read
Minimum Path Sum — Grid DP
Find minimum cost path from top-left to bottom-right moving right or down. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Read →
dsa1 min read
Triangle — Bottom-Up 1D DP
Minimum path sum from top to bottom of triangle. Bottom-up DP: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).
Read →
dsa1 min read
Longest Common Subsequence — LCS 2D DP
Classic LCS: dp[i][j] = LCS length of s1[:i] and s2[:j]. If chars match add 1 to diagonal; else take max of skip either string.
Read →
dsa1 min read
Edit Distance — Wagner-Fischer DP
Minimum operations (insert, delete, replace) to transform word1 to word2. Classic Wagner-Fischer 2D DP with O(n) space optimization.
Read →
dsa1 min read
Shortest Common Supersequence — LCS + Reconstruct
Find shortest string containing both strings as subsequences. Length = len(s1)+len(s2)-LCS. Reconstruct by tracing DP table.
Read →
dsa1 min read
Burst Balloons — Interval DP
Maximize coins by bursting balloons. Key insight: think of last balloon burst in interval [i,j]. dp[i][j] = max coins from interval with k as last balloon.
Read →
dsa1 min read
Best Time to Buy/Sell Stock I — Single Transaction
Maximize profit from a single buy-sell. Track running minimum price; at each day profit = price - min_so_far.
Read →
dsa1 min read
Best Time Buy/Sell Stock II — Unlimited Transactions
Maximize profit with unlimited buy-sell transactions (but hold at most 1 share). Greedy: collect every upward slope.
Read →
dsa1 min read
Best Time Buy/Sell Stock III — At Most 2 Transactions
Maximize profit with at most 2 transactions. Track 4 states: buy1, sell1, buy2, sell2. State machine DP.
Read →
dsa1 min read
Best Time Buy/Sell Stock IV — At Most k Transactions
At most k transactions. dp[t][i] = max profit using t transactions up to day i. If k >= n/2, unlimited transactions.
Read →
dsa1 min read
Best Time Buy/Sell Stock Cooldown — State DP
Unlimited transactions with 1-day cooldown after selling. 3-state DP: hold, sold (cooldown), rest.
Read →
dsa1 min read
Best Time Buy/Sell Stock With Fee — State DP
Unlimited transactions with transaction fee per sell. 2-state DP: cash (not holding) and hold (holding stock).
Read →
dsa1 min read
Interleaving String — 2D DP
Check if s3 is formed by interleaving s1 and s2. dp[i][j] = can s3[:i+j] be formed from s1[:i] and s2[:j].
Read →
dsa1 min read
Regular Expression Matching — 2D DP
Match string s against pattern p with . and *. dp[i][j] = does s[:i] match p[:j]. Handle * by matching zero or more of preceding char.
Read →
dsa1 min read
Wildcard Matching — 2D DP
Match string with wildcard pattern: ? matches any char, * matches any sequence. Similar to regex but * matches any sequence (not zero/more of preceding).
Read →
dsa1 min read
Dungeon Game — Reverse Grid DP
Find minimum initial health to reach bottom-right dungeon cell. Solve backwards: dp[i][j] = min health needed at (i,j) to survive.
Read →
dsa1 min read
Ones and Zeroes — 2D 0/1 Knapsack
Find maximum strings using at most m zeros and n ones. 2D 0/1 knapsack: dp[i][j] = max strings using i zeros and j ones.
Read →
dsa1 min read
Minimum Falling Path Sum — Grid DP
Find minimum sum falling path from top row to bottom row, moving to adjacent diagonal cells. DP row by row.
Read →
dsa1 min read
Strange Printer — Interval DP
Minimum turns to print string where each turn prints a contiguous run of same char. Interval DP: dp[i][j] = min turns for s[i..j].
Read →
dsa2 min read
2D Dynamic Programming — Master Recap & Cheatsheet
Complete 2D DP cheatsheet: 7 patterns, key transitions, stock state machine, interval DP template, and problem index.
Read →