Minimize adjacent-color assignment cost

You are given H linear items (e.g., houses) and an H×C cost matrix where cost[i][c] is the cost of assigning color c to item i. Adjacent items cannot share the same color. Design algorithms to compute the minimum total cost: (a) a top-down recursive solution with memoization and (b) a bottom-up dynamic program with space optimization. Return the minimum cost and also reconstruct one optimal assignment. Analyze time and space for C=3 and for general C, discuss how to reduce space to O(C), and cover edge cases (H=0, C=0/1, large costs).

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Minimize Adjacent-Color Assignment Cost (Paint House, general C)

You are given H linear items (e.g. houses) in a row and an H×C cost matrix cost, where cost[i][c] is the cost of painting item i with color c. No two ADJACENT items may share the same color. Return the minimum total cost to paint every item.

This generalizes LeetCode 'Paint House' (C=3) to any number of colors C. The intended solution is dynamic programming: let dp[i][c] be the minimum cost to paint items 0..i with item i colored c. Then dp[i][c] = cost[i][c] + min over c'≠c of dp[i-1][c']. A naive transition is O(H·C²); by tracking the smallest and second-smallest values of the previous row you reduce the transition to O(C), giving O(H·C) time and O(C) space (one rolling row). The same recurrence can also be written top-down with memoization.

Edge cases: H=0 (empty matrix) → cost 0; C=1 with H=1 → that single cell's cost (with H>1 and C=1 there is no valid coloring — by convention this implementation returns -1, but valid inputs have C≥2 whenever H≥2).

Implement minCost(cost) returning the minimum total cost as an integer.

Constraints

• 0 <= H <= 10^5 (number of items / rows)
• 1 <= C <= 100 (number of colors / columns) when H >= 1
• 0 <= cost[i][c] <= 10^6
• Every row of cost has exactly C entries
• Adjacent items (i and i+1) must receive different colors
• If H == 0 the answer is 0 (nothing to paint)

Examples

Example 1

Input: ([[17, 2, 17], [16, 16, 5], [14, 3, 19]],)
Output: 10

Explanation: Pick color1 (2) for item0, color2 (5) for item1, color1 (3) for item2 — no two adjacent share a color: 2 + 5 + 3 = 10, the minimum.

Example 2

Input: ([[7, 6, 2]],)
Output: 2

Explanation: Single item with no adjacency constraint — just take the cheapest color (2).

Hints

1. Define dp[i][c] = minimum cost to paint items 0..i with item i colored c. The transition only depends on the previous row, so you can keep just one rolling row → O(C) space.
2. dp[i][c] = cost[i][c] + min(dp[i-1][c'] for c' != c). Computing that min naively for every c is O(C²) per row.
3. Speed the transition to O(C): from the previous row, precompute the smallest value m1 (at color index i1) and the second-smallest value m2. For color c, the best predecessor is m1 unless c == i1, in which case it is m2.
4. Handle edges first: empty matrix → 0; a single row → min of that row; C == 1 only colorable when H <= 1.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You are given H linear items (e.g., houses) and an H×C cost matrix where cost[i][c] is the cost of assigning color c to item i. Adjacent items cannot share the same color. Design algorithms to compute the minimum total cost: (a) a top-down recursive solution with memoization and (b) a bottom-up dynamic program with space optimization. Return the minimum cost and also reconstruct one optimal assignment. Analyze time and space for C=3 and for general C, discuss how to reduce space to O (C), and cover edge cases (H=0, C=0/1, large costs).

Recommended Approach

Define a state that captures exactly the remaining decision information. Fill base cases first, then transition from smaller subproblems to larger ones. For games, use score difference or minimax DP; for counting, sum valid predecessor states.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Typical DP time is number_of_states times transition_cost. Space can often be reduced when transitions only need the previous layer or diagonal.

Edge Cases and Tests

Empty input, length 1, invalid symbols, negative values where allowed, ties under optimal play, and large counts requiring modulo arithmetic.