Blog
Mert Özen's blog posts on software development, backend, frontend, and DevOps.
Dynamic Programming 2: Real Problems with Edit Distance, LCS and Knapsack
Two-dimensional DP tables hold prefixes of two strings or a budget: Levenshtein for "did you mean?", LCS for a diff that matches git diff's output, and 0/1 knapsack for budget-limited campaign selection. We write all three in C#, measure a 20x speedup from bounded Levenshtein, show the loop-direction trap in one-row knapsack, and close the series with a pattern decision table.
Dynamic Programming 1: Memoization, Tabulation and Recognizing Subproblems
Dynamic programming turns an exponential computation into polynomial time by solving repeated subproblems once and storing them: naive Fibonacci makes 331 million calls for F(40), memoization 79. We measure memoization, tabulation and O(1)-memory versions in C#, solve climbing stairs, house robber and coin change with a five-step recipe, and show a wrong memo key and a stack overflow with real output.