There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.
costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...Return the minimum cost to paint all houses.
Example 1:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.
Example 2:
Input: costs = [[7,6,2]] Output: 2
Constraints:
costs.length == ncosts[i].length == 31 <= n <= 1001 <= costs[i][j] <= 20
The description was taken from https://leetcode.com/problems/paint-house/.
#O(M) Time, O(M) Space Since N is Constantly Three
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
m, n = len(costs), 3
dp = costs.copy() for row in range(1, m):
for col in range(n):
if col == 0:
dp[row][col] += min(dp[row-1][col+1], dp[row-1][col+2])
elif col == n-1:
dp[row][col] += min(dp[row-1][col-1], dp[row-1][col-2])
else:
dp[row][col] += min(dp[row-1][col-1], dp[row-1][col+1])
return min(dp[-1])This problem falls into the category of finding paths, similar problems include Minimum Path Sum, Minimum Falling Path Sum, Unique Paths, and Triangle.
To solve these types of problems, we'll arrive at point B and bring over the information from each point A that we could have traveled therefrom, based on the overall problem we are trying to solve. If the overall problem is trying to find the minimum noncontiguous path, for the matrix, then we can break the overall problem into subproblems by trying to find the minimum noncontiguous path to each cell. Each cell will be each individual subproblem.
Each subproblem will fall into three subcategories:
It is a left cell in which case the only noncontiguous subpath we could have gotten there from would be the top-right cell or the cell to the right of that.
It is a left cell in which case the only noncontiguous subpath we could have gotten there from would be the top-left cell or the cell to the left of that.
It is a cell not on any edge in which case the only contiguous subpath we could have gotten therefrom would be the top-left or the top-right cell.
With that intuition, all we need to do is divide each cell into one of these three categories through conditional statements and continuously find, then tabulate each path. Once we have done that, the minimum path would be carried to the last row.
Let's start by getting the length and width of the input matrix and saving it so that we don't have to keep rewriting this later.
m, n = len(costs), 3
We'll also want to make a copy of the matrix to build off of.
Technically we could perform this algorithm in place, but it's generally best practice to not do that for concurrency reasons.
dp = costs.copy()
For each row in the matrix starting from the second, since there is no path above the first row, we will go through each column and categorize each subproblem based on the aforementioned explanation.
for row in range(1, m):
for col in range(n):
If the current column is the first, we'll increment the current cell within our dp cache by the minimum value between the top-right and top-right-right cells.
if col == 0:
dp[row][col] += min(dp[row-1][col+1], dp[row-1][col+2])
If the current cell is the last, we'll increment the current cell within our dp cache by the minimum value between the top-left and top-left-left cells.
elif col == n-1:
dp[row][col] += min(dp[row-1][col-1], dp[row-1][col-2])
Otherwise, we'll increment the current cell within our dp cache by the minimum value between the top-left and the top-right cells.
else:
dp[row][col] += min(dp[row-1][col-1], dp[row-1][col+1])
Once we have tabulated each path, we will find the minimum one in the last row of our dp cache.
return min(dp[-1])
Since we are only utilizing the previous row for each subproblem, each row therebefore will be a waste of space.
We can drop this space complexity down to constant by only having two rows at a time, a total of six maximum cells always.
To do this, we will initialize the last row as the first row in the matrix. Then, we will initialize an empty row before we begin our traversal of each row. Once we are done building the new row at the end of each row traversal, we will set the new row as the last row. This way, we are only saving the last row in memory for each row traversal while we're building each new row.
#O(M) Time, O(1) Space Since N is Constantly Three
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
m, n = len(costs), 3
last_row = costs[0]
for row in range(1, m):
new_row = []
for col in range(n):
if col == 0:
new_row.append(costs[row][col] + min(last_row[col+1], last_row[col+2]))
elif col == n-1:
new_row.append(costs[row][col] + min(last_row[col-1], last_row[col-2]))
else:
new_row.append(costs[row][col] + min(last_row[col-1], last_row[col+1]))
last_row = new_row
return min(last_row)