LC: 256. Paint House
https://leetcode.com/problems/paint-house
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 house0with 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: 2Constraints:
costs.length == ncosts[i].length == 31 <= n <= 1001 <= costs[i][j] <= 20
The Essence:
Es ist zu bemerken, dass sich ein globales Optimum nicht immer aus einem lokales Optimum ergibt (vgl.: houses = [[1, 9, 18], [1, 999, 999]]).
Wenn man dann jede Möglichkeit mit 3 Farben für jeweilige Entscheidung rechnet, entsteht ein Entscheidungsbaum und damit eine Zeitkomplexität O(2^n).
Letztendlich kann man sehen, wie eine Entscheidung für ein Haus seinen Wert auf das nächste Haus überträgt: houses = [[1, 9, 18], [1, 999, 999]] ist gleich zu houses = [[1+9(previous 2. min), 999+1, 999+1]]. Diese Struktur kann Teilergebnisse von dem vorherigen Haus für das nächste verwenden. Also ist es notwendig, dass man betrachtet, wie Teilergebnisse die gesamte Lösung bestimmen.
Details:
Dieser Vorgang kann durch Schleife und Speicherung der vorherigen zwei Ergebnisse durchgeführt werden. Alles hier hat natürlich mit dem Thema Dynamische Programmierung, die besonders wichtig für solche Probleme ist, zu tun.
Solution:
Default Code:
Last updated