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 →
All Posts
1276 articles
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 →
Page 40 of 256