256. Paint House

第一个想法是：

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        f(k)
        color(k)
        ? l = k + 1
        f(l) = f(k) + cost(argmin([r, g, b] - color(k)))
        """

        pre = -1
        res = 0
        for cost in costs:
            idx = 0
            imin = cost[0]
            for i, c in enumerate(cost):
                if i == pre:
                    continue
                else:
                    if imin > c:
                        idx = i
                        imin = c

            res += imin
            pre = idx

        return res

上面这种想法，忽略了：[[17,2,17],[16,16,5],[14,3,19]] 每次有多个单次最优的解。

第二个想法，每次记录所有的 cost

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int

        """
        pre = [0,0,0]

        for cost in costs:
            pre = [cost[0] + min(pre[1:]), cost[1] + min(pre[0], pre[2]), cost[2] + min(pre[:2])]
        return min(pre)

这个思路的想法是，取之前的最小符合条件的值没有问题，但是当前的选取的最优值的下标，对后面的值的选择是有影响的。 如果只考虑当前的最优解，那么就会忽略下一个 cost 相同位置的值。

如 [[1, 200], [200, 500] 如果选择 costs[0][0]，第二个值必然是 costs[1][1]。显然是不合适的。