Contest-433 || Ques -3
PreRequisite - : https://leetcode.com/problems/paint-house-iii/solutions/6351580/dp-solution-memorization/Approach & IntuitionThis problem involves dynamic prog
### PreRequisite - : https://leetcode.com/problems/paint-house-iii/solutions/6351580/dp-solution-memorization/
### **Approach & Intuition**
This problem involves dynamic programming (DP) where the goal is to minimize the cost of coloring `n` elements while maintaining specific constraints on adjacent elements.

The approach used here is **"DP Starting from the Middle"**, meaning we process elements symmetrically from the center towards both ends.

#### **Key Observations**
1. **Symmetry**  
   - The given `cost` matrix has costs for painting elements at different indices.
   - Instead of solving from left to right, we start from the **middle** and assign colors symmetrically to both sides.

2. **State Definition (`dp[ind][adjRight][adjLeft]`)**  
   - `ind` → Current index we are processing (starting from the middle and going backward).
   - `adjRight` → Color assigned to the element at `ind + 1` (right neighbor).
   - `adjLeft` → Color assigned to the element at `n - ind` (symmetric left neighbor).
   - `dp[ind][adjRight][adjLeft]` stores the **minimum cost** to paint elements up to `ind`, ensuring no adjacent elements have the same color.

3. **Recurrence Relation**
   - We iterate over all possible colors for the current index (`i`).
   - We iterate over all possible colors for its symmetric counterpart (`j`).
   - We ensure:
     - `i` is not equal to `adjRight` (previous right element).
     - `j` is not equal to `i` and `adjLeft` (previous left element).
   - The cost for this configuration is:
     \[
     \text{cost}[ind][i-1] + \text{cost}[n - ind - 1][j-1] + \text{recursive call}
     \]
   - The answer is updated with the **minimum** cost found.

4. **Base Case**
   - If `ind < 0`, return `0` since there are no more elements to process.

### **Time & Space Complexity**
#### **Time Complexity:**
- **`ind` ranges from `n/2 - 1` to `0`** → `O(n)`.
- **Three choices for `i` (1 to 3)** → `O(3)`.
- **Three choices for `j` (1 to 3)** → `O(3)`.
- Total complexity:  
  \[
  O(n \times 3 \times 3) = O(9n) \approx O(n)
  \]
  which is **efficient**.

#### **Space Complexity:**
- The DP table `dp[n][4][4]` stores results for `n × 3 × 3 = 9n` states.
- Recursion stack uses `O(n)`.
- Total: **O(n)**.


# Code
```java []
class Solution {
    public long minCost(int n, int[][] cost) {
        
        long[][][] dp = new long[n+1][4][4];
        for(int i=0;i<=n;i++){
            for(int j=0;j<4;j++) Arrays.fill(dp[i][j],-1L);
        }
        return helper(n , cost , n/2 -1 , 0 , 0 ,dp );

        
        
    }
    long helper( int n , int[][] cost , int ind , int adjRight , int adjLeft , long[][][] dp){
        
        if(ind<0) return 0;
        
        if(dp[ind][adjRight][adjLeft]!=-1) return dp[ind][adjRight][adjLeft];
        long answer = (long)100000000000L;
        for(int i=1;i<=3;i++){
            if(i!=adjRight){
                for(int j=1;j<=3;j++){
                    if(j!=i && j!=adjLeft){
                        answer = Math.min(answer , (long)cost[ind][i-1]+(long)cost[n-ind-1][j-1] + (long)helper(n , cost , ind-1 , i ,j , dp));
                    }
                }
            }
        }
        return dp[ind][adjRight][adjLeft] = answer;
    }
}
```
['Dynamic Programming', 'Java']