Practice/LinkedIn/Leetcode 1473. Paint House III

Leetcode 1473. Paint House III

CodingOptional

Problem

You are planning the decoration scheme for a street with several buildings. Each building can be decorated with one of several color schemes, and some buildings may already be decorated (and cannot be changed).

Your goal is to decorate all undecorated buildings such that:

1. The total cost is minimized
2. The street has exactly a specified number of contiguous decoration zones

A zone is a maximal contiguous sequence of buildings with the same decoration scheme. For example, if buildings are decorated as [1, 1, 2, 2, 1], there are 3 zones: buildings 0-1 (scheme 1), buildings 2-3 (scheme 2), and building 4 (scheme 1).

Given:

• An array buildings where buildings[i] is either 0 (undecorated) or a positive integer representing its current decoration scheme
• The number of available decoration schemes
• A 2D array cost where cost[i][j] is the cost to decorate building i with scheme j+1
• The target number of zones

Return the minimum cost to achieve exactly the target number of zones, or -1 if it's impossible.

Requirements

1. You must decorate all buildings that have value 0 in the input array
2. Buildings with non-zero values are already decorated and cannot be changed
3. The final arrangement must have exactly the specified number of zones
4. Minimize the total decoration cost
5. Return -1 if it's impossible to achieve the target number of zones

Constraints

• 1 ≤ buildings.length ≤ 100
• 1 ≤ schemes ≤ 20
• 1 ≤ zones ≤ buildings.length
• 0 ≤ buildings[i] ≤ schemes
• cost.length = buildings.length
• cost[i].length = schemes
• 1 ≤ cost[i][j] ≤ 10,000
• schemes is the number of different decoration schemes available

Examples

Example 1:

` Input: buildings = [0, 0, 0, 0, 0] schemes = 3 cost = [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] zones = 3

Output: 3

Explanation: One optimal decoration is [1, 1, 2, 2, 3], which creates 3 zones:

• Zone 1: buildings 0-1 with scheme 1
• Zone 2: buildings 2-3 with scheme 2
• Zone 3: building 4 with scheme 3 Total cost: 1 + 1 + 1 = 3 `

Example 2:

` Input: buildings = [3, 1, 2, 3] schemes = 3 cost = [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] zones = 3

Output: -1

Explanation: All buildings are already decorated as [3, 1, 2, 3], forming 4 zones. Since we cannot repaint pre-decorated buildings, it's impossible to achieve exactly 3 zones. `

Example 3:

` Input: buildings = [1, 2, 2, 1] schemes = 2 cost = [[1, 2], [3, 4], [5, 6], [7, 8]] zones = 3

Output: 0

Explanation: Buildings form zones [1], [2], [1], which is exactly 3 zones. No decoration needed, so cost is 0. `