1473. Paint House III

 一刷 07/2022

Version #1 DP with optimized space

重点是每次一定要fill out array with -1，表示没有visit过的color和neighbor count都不能达成

这样才不会被0误update

Time O(Houses * Colors^2 * Target Neighbors)

Space O(Colors * Target Neighbors)

Runtime: 24 ms, faster than 88.44% of Java online submissions for Paint House III.

Memory Usage: 41.8 MB, less than 100.00% of Java online submissions for Paint House III.

class Solution {

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {

        // Min cost to paint the previous i houses, -1 means the house color is already set to other colors

        // dp[color][neighborCnt]

        int[][] dp = new int[n + 1][target + 1];

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

            int[][] ndp = new int[n + 1][target + 1];

            // zero neighborCnt is impossible

            for (int color = 1; color <= n; color++) {

                Arrays.fill(ndp[color], -1);

                for (int neighborCnt = 1; neighborCnt <= Math.min(i + 1, target); neighborCnt++) {

                    if (houses[i] != 0 && houses[i] != color) {

                        ndp[color][neighborCnt] = -1;

                        continue;

                    }

                    if (houses[i] != 0 && houses[i] == color) {

                        int minCost = Integer.MAX_VALUE;

                        for (int prevColor = 1; prevColor <= n; prevColor++) {

                            if (color == prevColor && dp[prevColor][neighborCnt] != -1) {

                                // the neighbor count is not changed

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

                            } else if (color != prevColor && dp[prevColor][neighborCnt - 1] != -1) {

                                minCost = Math.min(minCost, dp[prevColor][neighborCnt - 1]);

                            }

                        }

                        ndp[color][neighborCnt] = minCost == Integer.MAX_VALUE ? -1 : minCost;

                        continue;

                    }

                    // house is 0 and can be painted to any color with cost cost[i][color - 1]

                    int minCost = Integer.MAX_VALUE;

                    for (int prevColor = 1; prevColor <= n; prevColor++) {

                        if (color == prevColor && dp[prevColor][neighborCnt] != -1) {

                            minCost = Math.min(minCost, cost[i][color - 1] + dp[prevColor][neighborCnt]);

                        } else if (color != prevColor && dp[prevColor][neighborCnt - 1] != -1) {

                            minCost = Math.min(minCost, cost[i][color - 1] + dp[prevColor][neighborCnt - 1]);

                        }

                    }

                    ndp[color][neighborCnt] = minCost == Integer.MAX_VALUE ? -1 : minCost;

                }

            }

            dp = ndp;

        }

        int min = Integer.MAX_VALUE;

        for (int color = 1; color <= n; color++) {

            if (dp[color][target] == -1) {

                continue;

            }

            min = Math.min(min, dp[color][target]);

        }

        return min == Integer.MAX_VALUE ? -1 : min;

    }

}