Paint House

先是普通O(3n)的空间复杂度

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        n = len(costs)
        if not n:
            return 0

        m = len(costs[0])
        if not m:
            return 0

        dp = [[0] * 3 for _ in xrange(n)]
        for i in xrange(n):
            for j in xrange(m):
                if not i:
                    dp[i][j] = costs[i][j]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j - 2]) + costs[i][j]

        return min(dp[n - 1])

Paint House II

这道题就是把paint house I的3中颜色变成了k种，看起来就无法在O(1)时间找到当前状态的最优解了，但实际上仔细一想可以很容易看到，下一行的m - 1个点都会取上一行的最小值，而只有上一行最小值所在位置下面一行的点是不能加这个最小值的，而它应该加次小值，所以这道题关键解决思路就是要把每一行里面的最小值位置和次小值位置找到，而这个任务是可以在DP的同时一起完成的，而这道题其实最复杂的地方就是如何完美实现找最小值和次小值位置的逻辑，下面是自己的代码，逻辑太复杂不是很好看

class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        n = len(costs)
        if not n:
            return 0

        if n == 1:
            return min(costs[0])

        m = len(costs[0])
        if m <= 1 and n > 1:
            return 0

        minimum = 0
        sec_minimum = 1
        if costs[0][0] > costs[0][1]:
            minimum, sec_minimum = sec_minimum, minimum

        for i in xrange(2, m):
            if costs[0][i] < costs[0][minimum]:
                minimum, sec_minimum = sec_minimum, minimum
                minimum = i
            elif costs[0][i] < costs[0][sec_minimum]:
                sec_minimum = i

        res = costs[0][:]
        for i in xrange(1, n):
            cur_min = 0
            sec_cur_min = None
            tmp = res[:]
            for j in xrange(m):
                if j != minimum:
                    res[j] = costs[i][j] + tmp[minimum]
                else:
                    res[j] = costs[i][j] + tmp[sec_minimum]

                if j == 1:
                    if res[j] < res[cur_min]:
                        sec_cur_min = 0
                        cur_min = j
                    else:
                        sec_cur_min = j
                elif j > 1:
                    if res[j] < res[cur_min]:
                        cur_min, sec_cur_min = sec_cur_min, cur_min
                        cur_min = j
                    elif res[j] < res[sec_cur_min]:
                        sec_cur_min = j

            minimum = cur_min
            sec_minimum = sec_cur_min


        return min(res)

O(1)空间复杂度版本

class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        n = len(costs)
        if not n:
            return 0

        k = len(costs[0])
        if not k:
            return 0

        firstMin, secondMin = 0, 0
        firstIndex, secondIndex = None, None
        for i in xrange(n):
            tmpFirst, tmpSecond = sys.maxint, sys.maxint
            tmpFirIndex, tmpSecIndex = None, None
            for j in xrange(k):
                if j != firstIndex:
                    if costs[i][j] + firstMin < tmpFirst:
                        tmpSecond = tmpFirst
                        tmpSecIndex = tmpFirIndex
                        tmpFirIndex = j
                        tmpFirst = costs[i][j] + firstMin
                    elif costs[i][j] + firstMin < tmpSecond:
                        tmpSecond = costs[i][j] + firstMin
                        tmpSecIndex = j
                else:
                    if costs[i][j] + secondMin < tmpFirst:
                        tmpSecond = tmpFirst
                        tmpSecIndex = tmpFirIndex
                        tmpFirIndex = j
                        tmpFirst = costs[i][j] + secondMin
                    elif costs[i][j] + secondMin < tmpSecond:
                        tmpSecond = costs[i][j] + secondMin
                        tmpSecIndex = j

            firstMin, firstIndex = tmpFirst, tmpFirIndex
            secondMin, secondIndex = tmpSecond, tmpSecIndex

        return firstMin