256. Paint House

 一刷 07/2022

Version #1 DP with optimized space

Time O(9N) ~ O(N)

Space O(3) ~ O(1)

Runtime: 3 ms, faster than 19.21% of Java online submissions for Paint House.

Memory Usage: 44 MB, less than 19.33% of Java online submissions for Paint House.

class Solution {

    public int minCost(int[][] costs) {

        // min cost to paint to house i and house i has color c

        int[] dp = new int[3];

        for (int i = 0; i < costs.length; i++) {

            int[] ndp = new int[3];

            for (int c = 0; c < 3; c++) {

                int minCost = Integer.MAX_VALUE;

                for (int prevC = 0; prevC < 3; prevC++) {

                    if (prevC == c) {

                        continue;

                    }

                    minCost = Math.min(minCost, dp[prevC]);

                }

                ndp[c] = minCost + costs[i][c];

            }

            dp = ndp;

        }

        int min = Integer.MAX_VALUE;

        for (int c = 0; c < 3; c++) {

            min = Math.min(min, dp[c]);

        }

        return min;

    }

}