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).