Input:
costs =[[5]]
Output: 5
Explanation:
There is only one color and one house.

Challenge

Could you solve it in O(n*k).

Constraints

All costs are positive integers.

Solution

This problem is similar to Paint House 1 - N houses with 3 colors with no two adjacent houses with same color, but with k colors instead of 3.

Method 1 - Recursion

Code

[{"language":"Java","code":"class Solution {\n\n\tpublic int minCostII(int[][] costs) {\n\t\treturn minCostRecursive(costs, 0, -1);\n\t}\n\n\tprivate int helper(int[][] costs, int house, int lastColor) {\n\t\tif (house == costs.length) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tint min = Integer.MAX_VALUE;\n\n\t\tfor (int color = 0; color < costs[0].length; color++) {\n\t\t\tif (color != lastColor) {\n\t\t\t\tint cost = costs[house][color] + helper(costs, house + 1, color);\n\t\t\t\tmin = Math.min(min, cost);\n\t\t\t}\n\t\t}\n\n\t\treturn min;\n\t}\n}","lang":"java"}]

Method 2 - Top Down DP

Code

[{"language":"Java","code":"public class Solution {\n\n\tprivate Integer[][] memo;\n\n\tpublic int minCostII(int[][] costs) {\n\t\tmemo = new Integer[costs.length][costs[0].length];\n\t\treturn minCostRecursive(costs, 0, -1);\n\t}\n\n\tprivate int helper(int[][] costs, int house, int lastColor) {\n\t\tif (house == costs.length) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tif (lastColor != -1 && memo[house][lastColor] != null) {\n\t\t\treturn memo[house][lastColor];\n\t\t}\n\n\t\tint min = Integer.MAX_VALUE;\n\n\t\tfor (int color = 0; color < costs[0].length; color++) {\n\t\t\tif (color != lastColor) {\n\t\t\t\tint cost = costs[house][color] + helper(costs, house + 1, color);\n\t\t\t\tmin = Math.min(min, cost);\n\t\t\t}\n\t\t}\n\n\t\tif (lastColor != -1) {\n\t\t\tmemo[house][lastColor] = min;\n\t\t}\n\n\t\treturn min;\n\t}\n}","lang":"java"}]

Method 3 - DP

This is a classic back pack problem. - Define dp[n][k], where dp[i][j] means for house i with color j the minimum cost. - Initial value: dp[0][j] = costs[0][j]. For others, dp[i][j] = Integer.MAX_VALUE;, i >= 1 - Transit function: dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + cost[i][j]), where k != j. - Final state: Min(dp[n-1][k]).

Code

[{"language":"Java","code":"public int minCostII(int[][] costs) {\n\tif (costs == null || costs.length == 0) {\n\t\treturn 0;\n\t}\n\n\tint n = costs.length;\n\tint k = costs[0].length;\n\n\t// dp[i][j] means the min cost painting for house i, with color j\n\tint[][] dp = new int[n][k];\n\n\t// Initialize the first row of the DP table with the costs of painting the first house with each color\n\tfor (int color = 0; color < k; color++) {\n\t\tdp[0][color] = costs[0][color];\n\t}\n\n\tfor (int house = 1; house < n; house++) {\n\t\tfor (int color = 0; color < k; color++) {\n\t\t\tdp[house][color] = costs[house][color] + findMin(dp[house - 1], color);\n\t\t}\n\t}\n\n\t// Final state\n\tint minCost = Integer.MAX_VALUE;\n\n\tfor (int i = 0; i < k; i++) {\n\t\tminCost = Math.min(minCost, dp[n - 1][i]);\n\t}\n\n\treturn minCost;\n}","lang":"java"}]

Complexity

⏰ Time complexity: O(n*k*k)
🧺 Space complexity: O(n*k)

Method 4 - Space Optimized DP

Since dp[i][k] only depends on dp[i-1][j], we can use a 1-D DP solution.

Code

[{"language":"Java","code":"public int minCostII(int[][] costs) {\n\tif (costs == null || costs.length == 0) {\n\t\treturn 0;\n\t}\n\t \n\tint n = costs.length;\n\tint k = c

Related Tags