Paint House I/II
要点：这题要区分房子编号i和颜色编号k：目标是某个颜色，所以min的list是上一个房子编号中所有其他颜色+当前颜色的cost
https://repl.it/Chwe/1 (I)
- 善用slicing来eliminate list中一点，还有一点好处是不用考虑超越边界了
II：如何从O(nkk)降到O(n*k)? 每次找到上一个房子编号list的的min这个循环如果在每个k都做一遍，肯定是redundant的。其实loop一遍就能找到对所有颜色k需要的min：min和second_min：second_min用于min对应颜色的上一个房子
错误点：
- 注意不要搞混min/second_min的对象：因为当前颜色的cost是固定的。要min的是上一个房子编号的选择
- list comprehension: if else的优先级低于+，所以+两种可能之一要把if else加括号
- second_smallest的更新：如果smallest变了，第一件事是更新second_smallest，没变则比较second_smallest更新：所以是两处，并注意顺序
https://repl.it/Chxo/2 (II)
错误点：
- 小心k和循环下标混了
- 1d list就能搞定，因为下一个只依赖于前一个
# There are a row of n houses, each house can be painted with one of the 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 a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
# Note:
# All costs are positive integers.
# Hide Company Tags LinkedIn
# Hide Tags Dynamic Programming
# Hide Similar Problems (E) House Robber (M) House Robber II (H) Paint House II (E) Paint Fence
class Solution(object):
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
prev = [0]*3
for colors in costs:
prev = [colors[i] + min(prev[:i]+prev[i+1:]) for i in xrange(3)]
return min(prev)
sol = Solution()
assert sol.minCost([[1,2,3],[4,5,6],[7,8,9]])==13
# There are a row of n houses, each house can be painted with one of the k colors. 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 a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.
# Note:
# All costs are positive integers.
# Follow up:
# Could you solve it in O(nk) runtime?
# Hide Company Tags Facebook
# Hide Tags Dynamic Programming
# Hide Similar Problems (M) Product of Array Except Self (H) Sliding Window Maximum (M) Paint House (E) Paint Fence
class Solution(object):
def minCostII(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if not costs: return 0
n,k = len(costs), len(costs[0])
prev = [0]*k
for j in xrange(k):
prev[j]=costs[0][j]
for i in xrange(1, n):
minVal, secondMin = float("inf"), float("inf")
minIdx= -1
for j in xrange(k):
if prev[j]<minVal:
secondMin = minVal
minVal, minIdx = prev[j], j
elif prev[j]<secondMin:
secondMin = prev[j]
prev = [costs[i][j] + (minVal if j!=minIdx else secondMin) for j in xrange(k)]
return min(prev)
sol = Solution()
assert sol.minCostII([[1,5,3],[2,9,4]])==5
assert sol.minCostII([[1,2,3],[4,5,6],[7,8,9]])==13