Skip to content

265 Paint House II

265. Paint House II

题目: https://leetcode.com/problems/paint-house-ii/

难度:

Hard

思路:

感觉不像hard 题,知道为啥hard了,因为can you solve it in O(nk) runtime

数组 dp[x][k] 代表第x个房子paint 0..k的值

用paint house 1 改的AC代码:

不过这个时间复杂度是O(nkk)吧

class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        n = len(costs)
        if n == 0 : return 0
        elif n == 1 :  return min (costs[0])
        else:
            k = len(costs[0]) if n else 0
            dp = [[0 for i in range(k)] for j in range(n)]

            dp[0] = costs[0]

            for i in range(1,n):
                for j in range(0,k):
                    minVal = float('inf')
                    for m in range(0,k):
                        if m != j and dp[i-1][m] < minVal:
                            minVal = dp[i-1][m]
                    dp[i][j] = minVal + costs[i][j]

            return min(dp[-1])


回到顶部