✅DP & Tabulation | JAVA & C++| Easy Explanation!
IntuitionI had difficulty understanding the meaning of this line so why not discuss this firstthis means that there are three colors (1 , 2 , 3) that can be use
![Screenshot 2025-01-19 at 12.56.54 PM.png](https://assets.leetcode.com/users/images/9d8ff0c1-9fdd-4b62-b8d0-8aba4f5d6b68_1737273331.4671655.png)

# Intuition
I had difficulty understanding the meaning of this line so why not discuss this first 
```
cost[i][j] represents the cost of painting house i with color j + 1
```
this means that there are three colors (1 , 2 , 3) that can be used to paint the house on index i and will cost cost[i][0] , cost[i][1] , cost[i][2] respectively

We need to fulfill two conditions : 
- No two adjacent houses are painted the same color.
- Houses equidistant from the ends of the row are not painted the same color.

*For now lets forget the cost*

Now we try to fulfill these conditons 
**think of solving this problem in pairs**
lets pair up the houses that are equidistant from the front and from the back that is 
if n = 6 ,
(0 , 5) , (1 , 4) , (2 , 3) 

and paint these both houses simultaneously to avoid painting them same 

and we need to take care that the adjacent are not same 
so we need to have an instance of previous color of both sides for both houses 

# Approach
<!-- Describe your approach to solving the problem. -->

There are three colors 1 , 2 , 3
so we are pairing the hosues right 

then there will be (3*3 - 3) total possible pairs of painting two houses having three colors but you want them to be different 
**(1 , 1) , (2 , 2) , (3 , 3) rejected if you didnt get it**
we will try all possible pairs 
```
for(int j = 0 ; j < 3 ; j++){
    if(j != prev1) // this line save further computation 
    //Saving TLE
    for(int k = 0 ; k < 3 ; k++){
```
and keeping in mind that prev1 that is color of prevHouse from start 
and prev2 that is color of prevHouse at back 
is not same to color we are chososing now 
```
if(j != k && j != prev1 && k != prev2){
```
Now we will just find out the minimum costing by using recursions concept 
```
result = Math.min(result , cost[i][j] + cost[n-1-i][k] 
                        + solve(i+1 , j , k , n , cost));
```
Down below there is the tabulation (Bottom Up Approach) 

the same logic can be easily used for C++ 
that ill leave it to you 
upvote if helpful 
# Complexity
- Time complexity:
$$O(n*3*3)$$


# Code
```java []
class Solution {
    long dp[][][] ;
    public long minCost(int n, int[][] cost) {
        dp = new long[n][4][4];
        for(long[][] mat : dp){
            for(long[] row : mat) Arrays.fill(row , -1);
        }
        return solve(0 , 3 , 3 , n , cost);
    }
    long solve(int i , int prev1 , int prev2 , int n , int[][] cost){
        if( i >= n/2) return 0 ; 
        if(dp[i][prev1][prev2] != -1) return dp[i][prev1][prev2];

        long result = Long.MAX_VALUE ;

        for(int j = 0 ; j < 3 ; j++){
            if(j != prev1) // this line save further computation 
            //Saving TLE
            for(int k = 0 ; k < 3 ; k++){
                if(j != k && j != prev1 && k != prev2){
                    result = Math.min(result , cost[i][j] + cost[n-1-i][k] 
                    + solve(i+1 , j , k , n , cost));
                }
            }
        }

        return dp[i][prev1][prev2] = result ;
    }



    public long minCostII(int n, int[][] cost) {
        int numPairs = n / 2;
        List<int[]> pairs = new ArrayList<>(numPairs);
        
        for (int p = 0; p < numPairs; p++) {
            pairs.add(cost[p]);
        }

        long INF = (long)1e18;
        long[][] dpPrev = new long[3][3];

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                // System.out.println("OK");
                dpPrev[i][j] = INF;
            }
        }

        int i = 0 ;
        int j = n - 1;
        for (int c1 = 0; c1 < 3; c1++) {
            for (int c2 = 0; c2 < 3; c2++) {
                if (c1 != c2) {
                    long value = (long) cost[i][c1] + (long) cost[j][c2];
                    dpPrev[c1][c2] = value;
                }
            }
        }

        for (int p = 1; p < numPairs; p++) {
            i = p;
            j = n - 1 - p;
            long[][] dpCurr = new long[3][3];

            for (int c1 = 0; c1 < 3; c1++) {
                for (int c2 = 0; c2 < 3; c2++) {
                    dpCurr[c1][c2] = INF;
                }
            }

            for (int prevC1 = 0; prevC1 < 3; prevC1++) {
                for (int prevC2 = 0; prevC2 < 3; prevC2++) {
                    if (dpPrev[prevC1][prevC2] == INF) continue;

                    for (int c1 = 0; c1 < 3; c1++) {
                        for (int c2 = 0; c2 < 3; c2++) {
                            if (c1 != c2 && c1 != prevC1 && c2 != prevC2) {
                                long val = dpPrev[prevC1][prevC2] + (long) cost[i][c1] + (long) cost[j][c2] ;
                                dpCurr[c1][c2] = Math.min(dpCurr[c1][c2], val);
                            }
                        }
                    }
                }
            }

            for (int c1 = 0; c1 < 3; c1++) {
                for (int c2 = 0; c2 < 3; ++c2) {
                    dpPrev[c1][c2] = dpCurr[c1][c2];
                }
            }
        }

        long result = INF;
        for (int c1 = 0; c1 < 3; c1++) {
            for (int c2 = 0; c2 < 3; ++c2) {
                result = Math.min(result, dpPrev[c1][c2]);
            }
        }
        
        return result;
    }
}
```
```C++ []
class Solution {
public:
    using ll = long long;
    ll n, dp[(ll)1e5 + 5][4][4];

    ll solve(int i, int prev1, int prev2, int n, vector<vector<int>>& cost) {
        if (i >= n / 2) return 0;

        if (dp[i][prev1][prev2] != -1) return dp[i][prev1][prev2];

        ll result = LLONG_MAX;
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j != k && j != prev1 && k != prev2) {
                    result = min(result, 
                        cost[i][j] + 
                        cost[n - i - 1][k] + 
                        solve(i + 1, j, k, n, cost));
                }
            }
        }
        return dp[i][prev1][prev2] = result;
    }

    long long minCost(int n, vector<vector<int>>& cost) {
        this->n = n;
        for (int i = 0; i <= n / 2; ++i) {
            for (int j = 0; j < 4; ++j) {
                for (int k = 0; k < 4; ++k) {
                    dp[i][j][k] = -1;
                }
            }
        }
        return solve(0, 3, 3, n, cost);
    }
};
```
['Dynamic Programming', 'Memoization', 'Java']