dynamic programming

A DP classic that screens for one thing: can you define the right subproblem and fill the table without fumbling the indices. The strong version adds the O(min(m,n)) space trick and reconstructs the actual edits when the follow-up lands.

Almost everyone reaches the O(n²) DP. The signal interviewers want is the O(n log n) patience-sorting trick, plus the honesty to say the array you build along the way is not itself the answer subsequence.

The question that punishes greedy. Interviewers pick denominations where taking the biggest coin first gives the wrong answer, and they watch whether you reach for DP and handle the impossible-amount case cleanly.

The classic linear DP. At each house you either skip it and keep the best so far, or take it and add the best from two back. The signal is collapsing the table to two rolling variables and then handling the circular follow-up cleanly.

A path can start and end anywhere and bends through at most one node, values can be negative, and you want the maximum sum. The move is a DFS that returns the best downward gain (clamped at zero) while a global max tracks the best path that bridges through each node.