Tag: Dynamic Programming
3 posts
-
Dynamic Programming: Memoization vs Tabulation and How to Spot a DP Problem
Dynamic programming from first principles: when it is valid, defining the state, memoization vs tabulation, lru_cache recursion limits, and table sizing bugs.
-
DP Patterns: Defining the State, Choosing Loop Order, and Recognizing Knapsack, LCS, and LIS
Dynamic programming patterns explained through the decisions that make them work: what dp[i] means, why 0-1 knapsack loops backward, why loop order turns combinations into permutations, and why the LIS tails array is not the LIS.
-
DP Problem Walkthroughs: Make One, Knapsack, Edit Distance, LIS and Partition With Reconstruction
Worked DP problems from state to reconstruction: recovering the path, items and edit script, and why rolling arrays break reconstruction unless you keep choices.