Brute force recursion climb(n) = climb(n-1) + climb(n-2) is correct but makes about φⁿ ≈ 1.618ⁿ calls — n = 45 already needs over a billion. Every distinct n is solved once if we fill ways(1), ways(2), ... in increasing order, and because each cell reads only the two before it, two variables replace the whole array.

Trying every subset of non-adjacent houses is O(2ⁿ). Greedy choices fail — "always take the largest" picks 9 then cannot combine 7 and 3 in other inputs, and "take every other house" misses patterns like [2, 1, 1, 2] (answer 4 = first + last). The take/skip recurrence looks back only two positions, so two rolling variables give O(n) time and O(1) space.

Greedy "largest coin first" works for [1, 2, 5] but fails for coins [1, 3, 4] and amount 6: greedy gives 4+1+1 (3 coins), the optimum is 3+3 (2 coins). Plain recursion over last coins is exponential because amounts repeat. The table has amount + 1 cells, each trying every coin: O(amount × coins). Initialise with amount + 1 (more coins than could ever be needed) as a safe "infinity" that cannot overflow when we add 1.

Generating all decodings recursively is exponential (a string of 1s has Fibonacci-many decodings). Index the DP by prefix length so that dp[0] = 1 (the empty prefix has one, empty, decoding) — that base case makes the two-digit transition at i = 2 work without special code. Zeros are where bugs live: "0" alone is never valid, "10" and "20" are the only ways a zero can be used.

Recursive splitting re-checks the same suffix many times — "aaaa...ab" with words {"a", "aa", "aaa"} is exponential. With the boolean table each boundary is decided once. Two refinements: store the dictionary in a HashSet for O(1) membership, and only look back as far as the longest word, which caps the inner loop at L instead of n.

All 2ⁿ subsequences is hopeless. The O(n²) DP is the version to derive first in an interview. The patience-sorting version processes each x with one binary search: find the first tail ≥ x; if none, x extends the longest chain, otherwise x replaces that tail (same length, smaller ending — strictly better for the future). Using "≥" (lower bound) is what makes the subsequence strictly increasing.

Checking every subarray is O(n²) with a running product. A single running max fails on [-2, 3, -4]: after 3 it would forget the -6 that becomes 24. Tracking the pair of extremes keeps the state complete in O(1) per element. Zeros need no special case: the candidate x = 0 resets both extremes, and the next element starts fresh.

Backtracking over every jump length is exponential; the boolean DP is O(n²) because each index tries all its jump lengths. The greedy scan visits each index once: if the current index is beyond reach, it can never be visited, so return false; otherwise extend reach with i + nums[i]. This is the "greedy collapse" end of the DP spectrum — the DP argument is what proves the greedy correct.

Enumerating paths is exponential: there are C(m+n-2, m-1) of them. The grid table fills in O(mn). Since row r only reads row r-1, a single array of length n suffices: before the update dp[c] still holds "above", and dp[c-1] already holds "left". (A pure combinatorics answer also exists: choose which m-1 of the m+n-2 moves are downs.)

Brute force tries every monotone path (exponential). The table dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]) is O(mn); edges have only one predecessor. The original drill wrote the sums back into grid to get O(1) extra space — fast, but it destroys the caller's input. The version below keeps one row instead.

Checking every top-left corner and every size is O((mn)²) or worse. The recurrence makes each cell O(1). Padding the table with an extra zero row and column removes all edge checks. Track the maximum side while filling and square it at the end — the question asks for area.

Trying all 2ⁿ subsets is the brute force. The DP keeps dp[s] = "some subset of the items seen so far sums to s". For each item, sweep s from target down to the item value so dp[s - x] still refers to the previous round — the item is used at most once (Template B). An odd total is rejected immediately.

Brute force checks 2ⁿ subsequences. The interval table has n²/2 cells, each O(1). The fill order matters: dp[i][j] reads row i+1, so i must go from n-1 down to 0. The original drill instead computed the LCS of s and reverse(s) — also correct (an LPS is exactly a common subsequence of a string and its reverse) and also O(n²), but it builds an (n+1)² table and hides the interval idea that generalises to other problems.

The recursive version branches three ways per mismatch — O(3^m+n). The table over prefix pairs has (m+1)(n+1) cells: row 0 means "word1 is empty" (insert j chars) and column 0 means "word2 is empty" (delete i chars). Each cell is O(1), and walking back through the table recovers an actual edit script (green cells).