516. 房屋染色 II
中文English
这里有n个房子在一列直线上，现在我们需要给房屋染色，共有k种颜色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。
费用通过一个nxk 的矩阵给出，比如cost[0][0]表示房屋0染颜色0的费用，cost[1][2]表示房屋1染颜色2的费用。
样例
样例1
输入:
costs = [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
说明:
三个屋子分别使用第1,2,1种颜色，总花费是10。
样例2
输入:
costs = [[5]]
输出: 5
说明：
只有一种颜色，一个房子，花费为5
挑战
用O(nk)的时间复杂度解决
注意事项
所有费用都是正整数
输入测试数据 (每行一个参数)如何理解测试数据？
第一种写法，时间复杂度O(n*K**2),lintcode时间复杂度问题未通过
#房屋染色II class Solution: ''' 大致思路: 1. 确定状态 n*k 最后一步:dp[n - 1] 子问题:dp[n - 1][j] 2.转移方程,以只有三总染色颜色为例 dp[n][0] = min(dp[n - 1][1],dp[n - 1][2]) + costs[n][0] dp[n][1] = min(dp[n - 1][0],dp[n - 1][2]) + costs[n][1] dp[n][2] = min(dp[n - 1][0],dp[n - 1][1]) + costs[n][2] 3.初始条件和边界情况 dp = [[sys.maxsize]*k for _ in range(n)] if (i = 0): for j in range(k): dp[0][j] = costs[j] 4.计算顺序 for i in range(n): if (i = 0): for j in range(k): dp[0][j] = costs[j] #下面不用走了 continue for j in range(k): for z in range(k): if (z != j): #当前房子花费的钱，和上一个房子循环比较出花费最少的钱，最小值出来 dp[i][j] = min(dp[i - 1][z] + costs[j],dp[i][j]) ''' def minCostII(self, costs): if not costs or len(costs) == 0: return 0 #初始条件 n = len(costs) k = len(costs[0]) dp = [[sys.maxsize]*k for _ in range(n)] #计算顺序 for i in range(n): #因为是第一个房子的话，没有比较，所以，自然最小的是第一个房子染色所花费最少的 for j in range(k): if (i == 0): dp[0][j] = costs[i][j] continue for z in range(k): if (j != z): dp[i][j] = min(dp[i - 1][z] + costs[i][j], dp[i][j]) #取出最大值，最后一个房子的时候 return min(dp[n - 1]) #result = Solution().minCostII([[14,2,11],[11,14,5],[14,3,10]]) #print(result)
第二种写法：优化版本，时间复杂度O(n*k)
当前房屋只和上一个房屋的最小染色花费 + 次小染色花费 相加
如果当前房屋的染色 ！= 上一个房屋最小染色花费颜色 >> dp[i][j] = dp[i - 1][k] + min_num (首先先和上一个房屋染色花费最小的染色颜色进行比较，不同，则加)
如果当前房屋的染色 ! = 上一个房屋次小染色花费颜色 >> dp[i][j] = dp[i - 1][k] + second_min_num
##房屋染色，优化版本 ##题讲 动态规划常见优化，最小值，次小值 class Solution: ''' 大致思路： 1.当前房子染色的最小花费，循环当前房子的所有染色的花费 + 上一个房子染色的最小值 或者 次小值 min_num,second_min_num if 当前染的颜色 != 上一个染色(最小值): dp[i][k] = second_min_num + costs[i][k] else: dp[i][k] = min_num + costs[i][k] #最终形成的效果是 当前颜色为0的情况 ，dp[i][0] 染色的最小值 当前染色为1的情况 ，dp[i][1] 染色的最小值 当前染色为2的情况 ，dp[i][2] 染色的最小值 最终求出dp[i]的最小值即可，即为第i个房子的最小染色花费 ''' def minCostII(self, costs): if not costs or len(costs) == 0:return 0 #初始化 n = len(costs) k = len(costs[0]) dp = [[sys.maxsize]*k for _ in range(n)] for i in range(n): #初始化 if i == 0: for j in range(k): dp[0][j] = costs[i][j] continue #定义次小以及最小值,每次更新，避免是上一次的结果 min_num,second_min_num = sys.maxsize,sys.maxsize a,b = 0,0 #取出当前上一个房子的最小值和次小值,一次循环 for j in range(k): if dp[i - 1][j] < min_num: second_min_num = min_num min_num = dp[i - 1][j] b = a a = j elif dp[i - 1][j] < second_min_num: second_min_num = dp[i - 1][j] b = j #依次给当前房子，不同染色情况下进行赋值最小染色花费出来 for j in range(k): if j != a: dp[i][j] = min_num + costs[i][j] elif j != b: dp[i][j] = second_min_num + costs[i][j] #打印dp结果:[[14, 2, 11], [13, 25, 7], [21, 10, 23]] return min(dp[-1]) result = Solution().minCostII([[14,2,11],[11,14,5],[14,3,10]]) print(result)