← Static tasks

1473. Paint House III

leetcode hard

#array#csharp#dynamic-programming#hard#leetcode#math#matrix#recursion#search

Task

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].

Дан массив домов, матрица m x n стоимости и целое число target, где:

houses[i]: цвет дома i, и 0, если дом ещё не покрашен.

cost[i][j]: стоимость покраски дома i в цвет j + 1.

Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3

Output: 9

Explanation: Paint houses of this way [1,2,2,1,1]

This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].

Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

C# solution

matched/original
public class Solution {
    private const int MAX_COST = 1000001;
    private int[,,] memo = new int[100, 100, 21];
    private int FindMinCost(int[] houses, int[][] cost, int targetCount, int currIndex, int neighborhoodCount, int prevHouseColor) {
        if (currIndex == houses.Length) {
            return neighborhoodCount == targetCount ? 0 : MAX_COST;
        }
        if (neighborhoodCount > targetCount) {
            return MAX_COST;
        }
        if (memo[currIndex, neighborhoodCount, prevHouseColor] != 0) {
            return memo[currIndex, neighborhoodCount, prevHouseColor];
        }
        int minCost = MAX_COST;
        if (houses[currIndex] != 0) {
            int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
            minCost = FindMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
        } else {
            for (int color = 1; color <= cost[0].Length; color++) {
                int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
                int currCost = cost[currIndex][color - 1] + FindMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
                minCost = Math.Min(minCost, currCost);
            }
        }
        memo[currIndex, neighborhoodCount, prevHouseColor] = minCost;
        return minCost;
    }
    public int MinCost(int[] houses, int[][] cost, int m, int n, int target) {
        int answer = FindMinCost(houses, cost, target, 0, 0, 0);
        return answer == MAX_COST ? -1 : answer;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private const int MAX_COST = 1000001;
    private int[,,] memo = new int[100, 100, 21];
    private int FindMinCost(vector<int>& houses, int[][] cost, int targetCount, int currIndex, int neighborhoodCount, int prevHouseColor) {
        if (currIndex == houses.size()) {
            return neighborhoodCount == targetCount ? 0 : MAX_COST;
        }
        if (neighborhoodCount > targetCount) {
            return MAX_COST;
        }
        if (memo[currIndex, neighborhoodCount, prevHouseColor] != 0) {
            return memo[currIndex, neighborhoodCount, prevHouseColor];
        }
        int minCost = MAX_COST;
        if (houses[currIndex] != 0) {
            int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
            minCost = FindMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
        } else {
            for (int color = 1; color <= cost[0].size(); color++) {
                int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
                int currCost = cost[currIndex][color - 1] + FindMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
                minCost = min(minCost, currCost);
            }
        }
        memo[currIndex, neighborhoodCount, prevHouseColor] = minCost;
        return minCost;
    }
    public int MinCost(vector<int>& houses, int[][] cost, int m, int n, int target) {
        int answer = FindMinCost(houses, cost, target, 0, 0, 0);
        return answer == MAX_COST ? -1 : answer;
    }
}

Java solution

matched/original
class Solution {
    Integer[][][] memo = new Integer[100][100][21];
    final int MAX_COST = 1000001;
    
    int findMinCost(int[] houses, int[][] cost, int targetCount, int currIndex,
                    int neighborhoodCount, int prevHouseColor) {
        if (currIndex == houses.length) {
            return neighborhoodCount == targetCount ? 0 : MAX_COST;
        }
        
        if (neighborhoodCount > targetCount) {
            return MAX_COST;
        }
        
        if (memo[currIndex][neighborhoodCount][prevHouseColor] != null) {
            return memo[currIndex][neighborhoodCount][prevHouseColor];
        }
        
        int minCost = MAX_COST;
        if (houses[currIndex] != 0) {
            int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
            minCost = 
                findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
        } else {
            int totalColors = cost[0].length;
            
            for (int color = 1; color <= totalColors; color++) {
                int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
                int currCost = cost[currIndex][color - 1] 
                    + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
                minCost = Math.min(minCost, currCost);
            }
        }
        
        return memo[currIndex][neighborhoodCount][prevHouseColor] = minCost;
    }
    
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int answer = findMinCost(houses, cost, target, 0, 0, 0);
        return answer == MAX_COST ? -1 : answer;
    }
}

JavaScript solution

matched/original
class Solution {
    constructor() {
        this.MAX_COST = 1000001;
        this.memo = new Map();
    }

    findMinCost(houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor) {
        if (currIndex === houses.length) {
            return neighborhoodCount === targetCount ? 0 : this.MAX_COST;
        }

        if (neighborhoodCount > targetCount) {
            return this.MAX_COST;
        }

        const key = `${currIndex},${neighborhoodCount},${prevHouseColor}`;
        if (this.memo.has(key)) {
            return this.memo.get(key);
        }

        let minCost = this.MAX_COST;

        if (houses[currIndex] !== 0) {
            const newNeighborhoodCount = neighborhoodCount + (houses[currIndex] !== prevHouseColor ? 1 : 0);
            minCost = this.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
        } else {
            for (let color = 1; color <= cost[0].length; color++) {
                const newNeighborhoodCount = neighborhoodCount + (color !== prevHouseColor ? 1 : 0);
                const currCost = cost[currIndex][color - 1] + this.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
                minCost = Math.min(minCost, currCost);
            }
        }

        this.memo.set(key, minCost);
        return minCost;
    }

    minCost(houses, cost, m, n, target) {
        const answer = this.findMinCost(houses, cost, target, 0, 0, 0);
        return answer === this.MAX_COST ? -1 : answer;
    }
}

Python solution

matched/original
class Solution:
    def __init__(self):
        self.MAX_COST = 1000001
        self.memo = {}

    def findMinCost(self, houses, cost, targetCount, currIndex, neighborhoodCount, prevHouseColor):
        if currIndex == len(houses):
            return 0 if neighborhoodCount == targetCount else self.MAX_COST
        
        if neighborhoodCount > targetCount:
            return self.MAX_COST

        if (currIndex, neighborhoodCount, prevHouseColor) in self.memo:
            return self.memo[(currIndex, neighborhoodCount, prevHouseColor)]
        
        minCost = self.MAX_COST
        
        if houses[currIndex] != 0:
            newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor)
            minCost = self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        else:
            for color in range(1, len(cost[0]) + 1):
                newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor)
                currCost = cost[currIndex][color - 1] + self.findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = min(minCost, currCost)
        
        self.memo[(currIndex, neighborhoodCount, prevHouseColor)] = minCost
        return minCost
    
    def minCost(self, houses, cost, m, n, target):
        answer = self.findMinCost(houses, cost, target, 0, 0, 0)
        return -1 if answer == self.MAX_COST else answer

Go solution

matched/original
import (
    "math"
)

const MAX_COST = 1000001

type Solution struct {
    memo [101][101][21]int
}

func (this *Solution) findMinCost(houses []int, cost [][]int, targetCount, currIndex, neighborhoodCount, prevHouseColor int) int {
    if currIndex == len(houses) {
        if neighborhoodCount == targetCount {
            return 0
        } else {
            return MAX_COST
        }
    }

    if neighborhoodCount > targetCount {
        return MAX_COST
    }

    if this.memo[currIndex][neighborhoodCount][prevHouseColor] != 0 {
        return this.memo[currIndex][neighborhoodCount][prevHouseColor]
    }

    minCost := MAX_COST

    if houses[currIndex] != 0 {
        newNeighborhoodCount := neighborhoodCount
        if houses[currIndex] != prevHouseColor {
            newNeighborhoodCount++
        }
        minCost = this.findMinCost(houses, cost, targetCount, currIndex+1, newNeighborhoodCount, houses[currIndex])
    } else {
        for color := 1; color <= len(cost[0]); color++ {
            newNeighborhoodCount := neighborhoodCount
            if color != prevHouseColor {
                newNeighborhoodCount++
            }
            currCost := cost[currIndex][color-1] + this.findMinCost(houses, cost, targetCount, currIndex+1, newNeighborhoodCount, color)
            minCost = int(math.Min(float64(minCost), float64(currCost)))
        }
    }

    this.memo[currIndex][neighborhoodCount][prevHouseColor] = minCost
    return minCost
}

func minCost(houses []int, cost [][]int, m int, n int, target int) int {
    solution := Solution{}
    answer := solution.findMinCost(houses, cost, target, 0, 0, 0)
    if answer == MAX_COST {
        return -1
    }
    return answer
}

Explanation

Algorithm

Инициализация и базовые случаи:

Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.

Создайте метод findMinCost, который проверяет базовые случаи:

- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.

- если количество соседств больше target, возвращайте MAX_COST.

Если результат уже вычислен, возвращайте его из memo.

Рекурсивное вычисление минимальной стоимости:

Если дом уже покрашен, обновите количество соседств и вызовите рекурсивный метод для следующего дома.

Если дом не покрашен, попробуйте покрасить его в каждый возможный цвет, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Храните минимальную стоимость.

Метод minCost:

Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎