3 min read
Climbing Stairs: Where Dynamic Programming Starts
Fibonacci in costume — the recurrence-first discipline in miniature. Python solution and complexity analysis for the dynamic programming interview pattern.
Tag
Dynamic Programming
Articles tagged Dynamic Programming on The Augmented Dev.
11 articles
3 min read
Coin Change: Unbounded Choices, Minimum Count
Fewest coins to a target — and why greedy dies on [1, 3, 4]. Python solution and complexity analysis for the dynamic programming interview pattern.
4 min read
Edit Distance: The Capstone Two-String DP
Levenshtein distance — three operations, one table. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
House Robber: The Take or Skip Recurrence
Non-adjacent maximum sum — the two-variable rolling DP. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Jump Game: When Greedy Replaces the DP Table
Track the farthest reachable index — O(n) with one integer of state. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Longest Common Subsequence: The Grid That Explains Diffs
Match extends the diagonal, mismatch takes the better drop. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Longest Increasing Subsequence: From n² to n log n
The tails array and patience sorting — binary search inside DP. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Maximum Subarray: Kadane's Algorithm as One Line of DP
Extend or restart — the ending-here state that makes it one pass. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Partition Equal Subset Sum: 0/1 Knapsack in Disguise
Equal-halves split — subset-sum with the backward loop. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Unique Paths: Grid DP and the Rolling Row
Paths through a lattice — 2D recurrence, 1D memory. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Word Break: Segmentation as Reachability DP
Can the string be segmented? Prefix reachability with a set lookup. Python solution and complexity analysis for the dynamic programming interview pattern.