Leetcode 256 Minimum cost to paint house and additionally show the minimum colors to be print

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

 

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]

Output: 10

Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.

Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]

Output: 2

 

Constraints:

costs.length == n

costs[i].length == 3

1 <= n <= 100

1 <= costs[i][j] <= 20 

Top Down approach 

from functools import lru_cache
from typing import List, Tuple

class Solution:
    def minCost(self, costs: List[List[int]]) -> Tuple[int, List[int]]:
        n = len(costs)
        if n == 0:
            return 0, []

        @lru_cache(None)
        def dp(i: int, prev_color: int) -> int:
            if i == n:
                return 0

            min_cost = float('inf')
            for color in range(3):
                if color != prev_color:
                    cost = costs[i][color] + dp(i + 1, color)
                    if cost < min_cost:
                        min_cost = cost
            return min_cost

        # Reconstruct the path
        result_path = []
        prev_color = -1
        for i in range(n):
            min_cost = float('inf')
            best_color = -1
            for color in range(3):
                if color != prev_color:
                    cost = costs[i][color] + dp(i + 1, color)
                    if cost < min_cost:
                        min_cost = cost
                        best_color = color
            result_path.append(best_color)
            prev_color = best_color

        total_min_cost = dp(0, -1)
        return total_min_cost, result_path

Bottoms up approach 

class Solution:
    def minCost(self, costs: List[List[int]]) -> Tuple[int, List[int]]:
        if not costs:
            return 0, []
        
        n = len(costs)
        dp = [[0] * 3 for _ in range(n)]
        path = [[-1] * 3 for _ in range(n)]  # To reconstruct the color path

        # Base case
        for j in range(3):
            dp[0][j] = costs[0][j]

        # DP fill
        for i in range(1, n):
            for j in range(3):
                min_cost = float('inf')
                for k in range(3):
                    if j != k:
                        if dp[i-1][k] < min_cost:
                            min_cost = dp[i-1][k]
                            path[i][j] = k  # Store color used for previous house
                dp[i][j] = costs[i][j] + min_cost

        # Find the minimum cost and the color used at the last house
        min_total = min(dp[n-1])
        last_color = dp[n-1].index(min_total)

        # Reconstruct path
        result_path = [0] * n
        color = last_color
        for i in reversed(range(n)):
            result_path[i] = color
            color = path[i][color] if i > 0 else -1

        return min_total, result_path
        
'''
costs = [
    [17, 2, 17],
    [16, 16, 5],
    [14, 3, 19]
]

sol = Solution()
print(sol.minCost(costs))

(10, [1, 2, 1])

TC = O(n)
SC = O(n)
'''