forked from banjodayo39/LeetCode-Swift
-
Notifications
You must be signed in to change notification settings - Fork 0
/
PaintHouseII.swift
41 lines (33 loc) · 1.33 KB
/
PaintHouseII.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Question Link: https://leetcode.com/problems/paint-house-ii/
* Primary idea: Dynamic Programming, keep update previous min cost with its corresponding color
* and the second min cost.
*
* Note: DP with 2-D array will throw Time Limited Error
* Time Complexity: O(n), Space Complexity: O(1)
*/
class PaintHouseII {
func minCostII(_ costs: [[Int]]) -> Int {
guard let colors = costs.first, !colors.isEmpty else {
return 0
}
var preColor = -1, preMinCost = 0, preSecondMinCost = 0
for cost in costs {
var currentColor = -1, currentMinCost = Int.max, currentSecondMinCost = Int.max
for i in 0..<colors.count {
let sum = cost[i] + (preColor == i ? preSecondMinCost : preMinCost)
if sum < currentMinCost {
currentSecondMinCost = currentMinCost
currentMinCost = sum
currentColor = i
} else if sum < currentSecondMinCost {
currentSecondMinCost = sum
}
}
preColor = currentColor
preMinCost = currentMinCost
preSecondMinCost = currentSecondMinCost
}
return preMinCost
}
}