Rust solution
IntuitionThe problem revolves around finding the minimum cost of selecting colors for each pair of positions, such that adjacent colors do not repeat, and we wa
# Intuition
The problem revolves around finding the minimum cost of selecting colors for each pair of positions, such that adjacent colors do not repeat, and we want to minimize the overall cost. The problem has a recursive structure since we can break it down into subproblems based on the index and the color choices at previous positions. A dynamic programming approach is well-suited for this problem because it allows us to cache the results of subproblems to avoid redundant calculations.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
The approach to solving this problem involves using dynamic programming with memoization to compute the minimum cost of selecting colors for each pair of positions while adhering to the constraint that adjacent colors cannot be the same. The function f(i, left, right, n, cost, dp) recursively computes the minimum cost for the current index i, given the previously selected colors left and right. At each step, we explore all valid color pairs for the current and opposite positions and calculate the total cost, ensuring that no adjacent colors are the same. The results are stored in a 3D DP table to avoid redundant calculations. The final solution is obtained by starting the recursion with an invalid color (3) for the initial positions.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```rust []
impl Solution {
    fn f(i: usize, left: usize, right: usize, n: usize, cost: &Vec<Vec<i32>>, dp: &mut Vec<Vec<Vec<i64>>>) -> i64 {
        if i >= n / 2 {
            return 0;
        }
        
        if dp[i][left][right] != -1 {
            return dp[i][left][right];
        }

        let mut t = i64::MAX;
        for col1 in 0..3 {
            if col1 != left {
                for col2 in 0..3 {
                    if col2 != right && col2 != col1 {
                        let q = cost[i][col1] as i64 + cost[n - 1 - i][col2] as i64 + Solution::f(i + 1, col1, col2, n, cost, dp);
                        t = t.min(q);
                    }
                }
            }
        }

        dp[i][left][right] = t;
        t
    }

    pub fn min_cost(n: i32, cost: Vec<Vec<i32>>) -> i64 {
        let n = n as usize;
        let mut dp = vec![vec![vec![-1; 4]; 4]; n];

        Solution::f(0, 3, 3, n, &cost, &mut dp)
    }
}

```
['Array', 'Dynamic Programming', 'Rust']