dp基础之序列型油漆房子

问题：有一排N栋房子，每栋房子要油漆成红、蓝、绿三种颜色，第i栋房子油漆成红、蓝、绿的花费分别为cost[i][0]、cost[i][1]、cost[i][2]
要求：相邻的房子颜色需不同
求油漆好房子的最小花费

 

代码及注释如下：

def Pint_huose(cost):
    #N是房子的个数，K是油漆的颜色种数
    N,K = len(cost),len(cost[0])
    #f[i][j]表示油漆前i个房子并且房子i-1是颜色j的最小花费，因为求最小，所以都先设置成大数
    f = [[sys.maxsize for x in range(K)] for y in range(N+1)]
    #初始条件
    for z in range(K):
        f[0][z] = 0
    for i in range(1,N+1):
        #从前1栋房子到前N栋房子
        for j in range(K):
            #j是房子i-1的颜色
            for k in range(K):
                #k是房子i-2使用的颜色
                if j == k:
                    #如果房子i-1的颜色和前面的房子同色，则略过
                    continue
                if f[i-1][k] + cost[i-1][j] < f[i][j]:
                    #f[i-1][k]表示油漆前i-1栋房子并且房子i-1使用颜色k的最小花费
                    #cost[i-1][j]表示房子i-1用颜色j油漆的花费
                    #如果房子油漆前i-1个房子且房子i-2用颜色k,房子i-1用颜色j来油漆的最小花费，小于前i栋房子的花费，则更新f[i][j],因为这里f[i][j]初始值是最大，所以，每次取最小值
                    f[i][j] = f[i-1][k] + cost[i-1][j]
    #最后返回油漆前N个房子并且房子N用某种颜色的最小花费
    return min(f[N])

cost = [[14,2,11],
        [11,14,5],
        [14,3,10]]
print(Pint_huose(cost))
结果：10    

若是K种颜色，f[i][j]表示油漆前i个房子并且房子i-1是颜色j的最小花费
f[i][j] = min{f[i-1][k]+cost[i][j]}(k!=j)
时间复杂度:
i=1,2,...N
j=0,1,2,...K
k=0,1,2...K
为O(N*K*K)
但实质上，
上式中f[i][j] = min{f[i-1][k]+cost[i][j]}(k!=j)是在一个序列中寻找除k!=j之外里的最小元素，怎么说，当i和j固定，f[i][j] = min{f[i-1][k]}+cost[i][j](k!=j),相当于求f[i-1][k]里中除了一个元素（k!=j那个元素）以外的最小元素，其实k是不用从0循环到K的

例如：序列为A = [3,1,24,5，6]。求A[i]中除了i=0,1,2...4,以外的最小元素。当i =0是，因为最小元素是1，3不是最小元素那么除 3以外序列中最小元素还是1，当i = 1时，此时除掉1以为的最小元素就是5（次小元素）了，当i= 2时，即除了24以外的最小元素还是1，同理当求i=3,4时发现最小元素还是1是不变的。故我们可以得到如下规律。只要发现除掉一个的那个元素以外的序列中的最小元素不是原来序列中的最小元素,则最小元素的就是原来的最小元素,如果是，则此时最小值是次小值元素
对应于上面问题，求f[i-1][k]里中除了一个元素（k!=j那个元素）以外的最小元素，时间复杂度是k不用从0到K,是可以优化到常数时间，只要求出最小值和次小值后进行判断即可

故时间复杂度可以从O（N*K*K）降到O(N*K)

 

代码及注释如下：

def Pint_K_huose(cost):
    #N是房子的个数，K是油漆的颜色种数
    N,K = len(cost),len(cost[0])
    #f[i][j]表示油漆前i个房子并且房子i-1是房子j的最小花费，因为求最小，所以都先设置成大数
    f = [[sys.maxsize for x in range(K)] for y in range(N+1)]
    #初始条件,前0栋房子的花费都是0
    for z in range(K):
        f[0][z] = 0
    for i in range(1,N+1):
        #从前1栋房子到前N栋房子
        #前i栋房子里，每次先求出f[i-1][0]到f[i-1][k]的最小值min1和次小值min2
        min1 ,min2 = sys.maxsize,sys.maxsize
        #j1,j2分别表示最小值和次小值的下标
        j1,j2 = 0,0
        for j in range(K):
            if f[i-1][j] < min1:
                min2 = min1
                j2 = j1
                min1 = f[i-1][j]
                j1 = j
            else:
                if f[i-1][j] < min2:
                    min2 = f[i-1][j]
                    j2 = j
        
        for j in range(K):
            #判断所要除去的那个元素是不是最小值
            if j != j1:
                #如果不等于最小值，此时序f[i-1][j]
                f[i][j] = f[i-1][j1]+cost[i-1][j]
            else:
                #如果等于最小值，则此时最小值为次小值
                f[i][j] = f[i-1][j2]+cost[i-1][j]
                
    return min(f[N])

cost = [[14,2,11],
        [11,14,5],
        [14,3,10]]
print(Pint_K_huose(cost))
结果是10