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

        def dfs(i, prevColor):
            if i == n:
                return 0

            res = float("inf")
            for c in range(3):
                if c == prevColor:
                    continue
                res = min(res, costs[i][c] + dfs(i + 1, c))
            return res

        return dfs(0, -1)

class Solution:
    def min_cost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        dp = [[-1] * 4 for _ in range(n)]

        def dfs(i, prevColor):
            if i == n:
                return 0
            if dp[i][prevColor + 1] != -1:
                return dp[i][prevColor + 1]

            res = float("inf")
            for c in range(3):
                if c == prevColor:
                    continue
                res = min(res, costs[i][c] + dfs(i + 1, c))

            dp[i][prevColor + 1] = res
            return res

        return dfs(0, -1)

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

        dp = [[0] * 3 for _ in range(n)]
        for c in range(3):
            dp[0][c] = costs[0][c]

        for i in range(1, n):
            for c in range(3):
                dp[i][c] = (
                    costs[i][c] +
                    min(dp[i - 1][(c + 1) % 3], dp[i - 1][(c + 2) % 3])
                )

        return min(dp[n - 1])

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        dp = [0, 0, 0]

        for i in range(len(costs)):
            dp0 = costs[i][0] + min(dp[1], dp[2])
            dp1 = costs[i][1] + min(dp[0], dp[2])
            dp2 = costs[i][2] + min(dp[0], dp[1])
            dp = [dp0, dp1, dp2]

        return min(dp)