dynamic programming

DP feels like pattern-matching magic until you have a method. The signal is a repeatable drill: spot overlapping subproblems and optimal substructure, define the state and recurrence, then memoize or tabulate. Here is that method on a worked example.

Edit distance is the canonical 2D string DP, behind spell-check, diff, and fuzzy matching. The signal is defining the subproblem and the insert/delete/replace recurrence. Here is the answer.

Maximum subarray is the gateway 1D DP problem, and Kadane's is the O(n) one-liner. The signal is the 'extend or restart' decision at each element and the all-negative edge case most people botch. Here is the answer.

Word Break is the classic 1D string DP that trips people who reach for greedy or naive recursion. The signal is the dp[i] = 'is the prefix of length i segmentable' recurrence, plus why a locally valid split can doom the rest. Here is the answer.

The DP that exposes why greedy quietly breaks on non-standard denominations, and how one bottom-up table fixes it. The signal interviewers want is the dp[amount] recurrence and the unbounded-reuse insight.

LCS is the template 2D-sequence DP behind diff tools and bioinformatics. The signal is reconstructing the match/mismatch recurrence cold and not confusing subsequence (gaps allowed) with substring (contiguous). Here is the answer.

LIS has an obvious O(n²) DP and a clever O(n log n) solution that surprises people. The signal is the patience-sorting/binary-search approach maintaining 'tails'. Here is both.

House Robber is the cleanest choose-with-a-constraint 1D DP, and it collapses to O(1) space. The signal is the take-this-or-skip recurrence and the two-variable rolling optimization.

The canonical grid DP where each cell depends on three neighbors at once. The signal interviewers want is the min-of-three recurrence, and the reason it has to be min. Here is the answer.

Decode Ways is a 1D DP whose difficulty lives entirely in the edge cases: zeros and the valid 1-26 range. The signal is the take-one-digit-or-two recurrence plus disciplined validity checks. Here is the answer.

Negative subtrees, a path that bends through any node, and a return value that differs from the answer you track: this problem packs three traps into one DFS. Here is the clean O(n) solution and the reasoning that survives follow-ups.

Floyd-Warshall computes shortest paths between every pair of nodes in O(V cubed) with a tight three-line triple loop. The signal is the intermediate-node DP order and why k must be the outer loop. Here is the answer.

HMMs are the classic probabilistic sequence model behind speech and tagging, and Viterbi is how you decode them. The signal is the hidden-states plus transitions/emissions structure, and that Viterbi is dynamic programming for the single best state path, not a probability.