Simplest DP python explanation
IntuitionThink in terms of immediate dependency at each step. The current color depends on both the previous color as well as the color at the opposite end. Thi
# Intuition

Think in terms of immediate dependency at each step. The current color depends on both the previous color as well as the color at the opposite end. This make dynamic programming a good choice.
<!-- Describe your first thoughts on how to solve this problem. -->
Since the choice of color at index i will limit our choice of color for index n-1-i, we add index n-1-i as part of our DP state.


# Approach
<!-- Describe your approach to solving the problem. -->
At each index i in the DP, we store cost[i][j]+cost[n-1-i]. Therefore, DP[i] represents the sum of cost to get from 0 to index i for optimum color choices from the left and n-i-1 to n-1 for optimum color choices from the right.

As such, we only need to reach index n//2 to compute the total minimum cost.



# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
linear
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
linear
# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        @lru_cache
        def solve(i,prev_color,prev_last_color):
            if i>=(n//2):
                return 0
            minimum=float('inf')
            for j in range(3):
                if j!=prev_color:
                    for k in range(3):
                        if k!=prev_last_color and k!=j:
                            minimum=min(minimum,cost[i][j]+cost[n-1-i][k]+solve(i+1,j,k))
            return minimum
        return solve(0,-1,-1)
```
['Python3']