LeetCode 265. Paint House II Python3
原题链接
困难
作者:
leo173701
,
2019-09-25 04:45:49
,
所有人可见
,
阅读 946
算法1
DP Time O(n*k^2), space O(k)
Python3 代码
class Solution(object):
def minCostII(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
n = len(costs)
if n==0:
return 0
if n==1:
return min(costs[0])
m = len(costs[0])
now = [0 for _ in range(m)]
dp = costs[0]
for i in range(1,n):
for j in range(m):
temp2 = min([dp[k] for k in range(m) if k!=j])
now[j] = temp2 + costs[i][j]
dp[:] = now[:]
return min(dp)
算法2
DP Time O(n*k), space O(1)
Python3 代码
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])
for i in range(1,n):
min1 = min(costs[i-1])
index = costs[i-1].index(min1)
min2 = min(costs[i-1][:index] + costs[i-1][index+1:] )
for j in range(k):
if j == index:
costs[i][j] += min2
else:
costs[i][j] += min1
return min(costs[-1])