256. Paint House

n colors solutions, traditional DP

time: O(3m), costs' matrix size(3 colors), if n colors, it will be O(mn)

space: O(3m)

class Solution {
    public int minCost(int[][] costs) {
        // one of three colors, R G B
        // that no two adjacent houses have the "same" color.
        // costs[house_index][color_type]
        
        // dp[i][0] = costs[i][0] + dp[i][1 or 2]
        // dp[i][1] = costs[i][1] + dp[i][0 or 2]
        // dp[i][2] = costs[i][2] + dp[i][1 or 3] 
        // ... j color       
        // dp[i][j] = costs[i][j] + dp[i][color_type excludes j]
        
        if (costs == null || costs.length == 0) return 0;
        
        int m = costs.length;
        int n = costs[0].length;
        int dp[][] = new int[m][n];
                
        for(int k = 0; k < n ; k++) {
            dp[0][k] = costs[0][k];
        }

        for (int i = 1; i < m; i++) {
            for(int j = 0; j < n ; j++) { // 0 1 2,   n colors
                dp[i][j] = costs[i][j] + findMinColor(i-1, j, dp); // use j color
            }
        }
        
        return findMinColor(m-1, -1, dp); // use -1 means, no needs to exclude colors
    }
    private int findMinColor(int i, int j, int dp[][]) { // cant use j color
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < dp[0].length; k++) { // loop n colors again
            if (k != j) {
                min = Math.min(min, dp[i][k]);
            }
        } 
        return min;
    }
}

use variables

time: O(m)

space: O(1)

class Solution {
    public int minCost(int[][] costs) {
        // one of three colors, R G B
        // that no two adjacent houses have the "same" color.
        // costs[house_index][color_type]
        // dp[i-1][0] + costs[i][1~2]
        
        if (costs == null || costs.length == 0) return 0;
        
        int m = costs.length;
        
        int r = 0;
        int g = 0;
        int b = 0;
    
        for (int i = 0; i < m; i++) {
            int rr = r, gg = g, bb = b;
            r = costs[i][0] + Math.min(gg, bb);
            g = costs[i][1] + Math.min(rr, bb);
            b = costs[i][2] + Math.min(rr, gg);
        }        
        return Math.min(r, Math.min(g, b));
    }
}