ByteInTheSky

Paint House

Tagged: Array, Dynamic Programming

Problem

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.

  • For example, 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.

For example,

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.

Input: costs = [[7,6,2]]
Output: 2

Constraints:

  • costs.length == n
  • costs[i].length == 3
  • 1 <= n <= 100
  • 1 <= costs[i][j] <= 20

Solution

Brute Force

public int MinCost(int[][] costs)
{
    return Math.Min(PaintCost(0, 0), Math.Min(PaintCost(0, 1), PaintCost(0, 2)));

    int PaintCost(int i, int color)
    {
        int totalCost = costs[i][color];

        if (i == costs.Length - 1)
        {

        }
        else if (color == 0)    // Red
        {
            totalCost += Math.Min(PaintCost(i + 1, 1), PaintCost(i + 1, 2));
        }
        else if (color == 1)    // Blue
        {
            totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 2));
        }
        else if (color == 2)    // Green
        {
            totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 1));
        }

        return totalCost;
    }
}

Complexity Analysis

Suppose N is the length of costs.

  • Time Complexity: At each step we generate two subtree and the height of the tree is N. The total number of generated nodes is 2N. Since, we traverse all the nodes, then the complexity will be O(2N).
  • Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(N).

Top-down Dynamic Programming

public int MinCost(int[][] costs)
{
    Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();
    return Math.Min(PaintCost(0, 0), Math.Min(PaintCost(0, 1), PaintCost(0, 2)));

    int PaintCost(int i, int color)
    {
        if (memo.TryGetValue((i, color), out int value))
        {
            return value;
        }

        int totalCost = costs[i][color];

        if (i == costs.Length - 1)
        {

        }
        else if (color == 0)    // Red
        {
            totalCost += Math.Min(PaintCost(i + 1, 1), PaintCost(i + 1, 2));
        }
        else if (color == 1)    // Blue
        {
            totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 2));
        }
        else if (color == 2)    // Green
        {
            totalCost += Math.Min(PaintCost(i + 1, 0), PaintCost(i + 1, 1));
        }

        memo.Add((i, color), totalCost);

        return totalCost;
    }
}

Complexity Analysis

Suppose N is the length of costs.

  • Time Complexity: Since we cache each PaintCost(i,color), then we will perform at most N recursive calls, thus the complexity is O(N).
  • Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(N).

Bottom-up Dynamic Programming

public int MinCost(int[][] costs)
{
    for (int n = costs.Length - 2; n >= 0; n--)
    {
        // Total cost of painting the nth house red.
        costs[n][0] += Math.Min(costs[n + 1][1], costs[n + 1][2]);

        // Total cost of painting the nth house blue.
        costs[n][1] += Math.Min(costs[n + 1][0], costs[n + 1][2]);

        // Total cost of painting the nth house green.
        costs[n][2] += Math.Min(costs[n + 1][0], costs[n + 1][1]);
    }

    return Math.Min(costs[0][0], Math.Min(costs[0][1], costs[0][2]));
}

Complexity Analysis

Suppose N is the length of costs.

  • Time Complexity: Since we iterate linearly up to N, then the complexity is O(N).
  • Space Complexity: O(1) since we only need to reuse the input costs array.
← Paint Fence
Delete and Earn →