[LeetCode]Paint House II

用DP[i][k]代表第i个房子用第k个颜色paint情况下，总的cost最小的值。那么我们有递推公式：

• DP[i][k] = cost[i][k] + min(DP[i - 1][j]), where j != k

我们当然可以用滚动数组来优化，但是这样的话对于n * k个值，每一个值我们要k的时间去求min(DP[i - 1][j])，时间复杂度是O(n * k ^ 2)。我们还可以继续优化，其实对于每一个k来说，我们从之前的房子所需要的值只有之前房子的最小cost并且最小cost对应的color不为k，假设color为k，我们就取第二小的值。也就是说，我们只需要维护从上一个房子得到的最小cost，第二小cost和他们对应的color就可以了。这两个值我们在求DP[i][0->k]的时候就可以一直维护，所以总的时间按复杂度可以降低到O(n * k)，常数空间。代码如下：