Python | Beat 100% | Clean and Fast Code with Comments | Bottom-Up Dynamic Programming
IntuitionStart to paint from the two ends, and paint toward the middle. We then can observe that this can be split into subproblems, so use dynamic programming.
![image.png](https://assets.leetcode.com/users/images/01129ee5-ae59-4770-86bb-e30e9acd2838_1737369649.4010913.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Start to paint from the two ends, and paint toward the middle. We then can observe that this can be split into subproblems, so use dynamic programming.

# Approach
<!-- Describe your approach to solving the problem. -->
`dp[i][j][k]`
* The minimum cost to paint both ends from 0 to i and from n - 1 to n - 1 - i. 
* The i-th house is painted color j.
* The (n - 1 - i)-th house is painted color k.

We can simply enumerate all possible color combination of the current pair and the previous pair as there are only 3 colors. 
The answer of the original problem would be the minimum value in `dp[n // 2]`.

# Complexity
- Time complexity: $O(81 \times n / 2) = O(n)$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: 
    - Original: $O(9 \times n / 2) = O(n)$
    - Optimized: $O(9 \times 2) = O(1)$. (as we only need the previous pair's result to calculate the current pair)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
## Original Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        # dp[i][j][k]: 
        # The minimum cost to paint both ends from 0 to i and from n - 1 to n - 1 - i. 
        # The i-th house is painted color j.
        # The (n - 1 - i)-th house is painted color k.
        dp = [
            [[float("inf") for k in range(3)] for j in range(3)] for i in range(n // 2)
        ]

        # Paint from both ends toward middle.
        for i in range(n // 2):

            # Enumerate all possible color combinations
            for j in range(3):
                for k in range(3):
                    
                    # Equidistant houses from the ends should have different color.
                    if j == k:
                        continue

                    dp[i][j][k] = cost[i][j] + cost[n - 1 - i][k]
                    if i != 0:
                        # Enumerate all possible color combination of previous pair,
                        # but adjacent houses should have different color.
                        dp[i][j][k] += min(
                            dp[i - 1][l][m]
                            for l in range(3)
                            for m in range(3)
                            if l != m and l != j and m != k
                        )

        return min(min(v) for v in dp[n // 2 - 1])
```

## Space Optimized

```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        # dp[i][j][k]:
        # The minimum cost to paint both ends from 0 to i and from n - 1 to n - 1 - i.
        # The i-th house is painted color j.
        # The (n - 1 - i)-th house is painted color k.
        # dp = [
        #     [[float("inf") for k in range(3)] for j in range(3)] for i in range(n // 2)
        # ]

        prev = [[0] * 3 for _ in range(3)]
        curr = [[float("inf")] * 3 for _ in range(3)]

        # Paint from both ends toward middle.
        for i in range(n // 2):

            # Enumerate all possible color combinations
            for j in range(3):
                for k in range(3):

                    # Equidistant houses from the ends should have different color.
                    if j == k:
                        continue

                    curr[j][k] = (
                        cost[i][j]
                        + cost[n - 1 - i][k]
                        + min(
                            prev[l][m]
                            for l in range(3)
                            for m in range(3)
                            if l != m and l != j and m != k
                        )
                    )

            prev = curr
            curr = [[float("inf")] * 3 for _ in range(3)]

        return min(min(v) for v in prev)
```

## Without Comments
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        prev = [[0] * 3 for _ in range(3)]
        curr = [[float("inf")] * 3 for _ in range(3)]

        for i in range(n // 2):
            for j in range(3):
                for k in range(3):
                    if j == k:
                        continue

                    curr[j][k] = (
                        cost[i][j]
                        + cost[n - 1 - i][k]
                        + min(
                            prev[l][m]
                            for l in range(3)
                            for m in range(3)
                            if l != m and l != j and m != k
                        )
                    )

            prev = curr
            curr = [[float("inf")] * 3 for _ in range(3)]

        return min(min(v) for v in prev)
```
['Dynamic Programming', 'Python3']