序列型动态规划——粉刷房子

痛定思痛。 2022-10-27 06:26 164阅读 0赞

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如，costs\[0\]\[0\] 表示第 0 号房子粉刷成红色的成本花费；costs\[1\]\[2\] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[17,2,17],[16,16,5],[14,3,19]]
    输出: 10
    解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
         最少花费: 2 + 5 + 3 = 10。

### 1、题目分析 ###

从题目的提问方式中应该能看出该题目是典型的最值型动态规划问题。

### 2、确定状态 ###

我们的最终目的是为了使得粉刷完所有的房子花费最少的成本。直接套用以前的思路，记录油漆前N栋房子的最小花费。，同时我们还需要记录油漆前N-1栋房子的最小花费。但是存在一个问题，前N-1栋房子的最小花费中，不知道房子N-2是什么颜色。其实这个问题很好处理，直接把它记录下来开一个数组分别记录前N-1栋房子并且N-2栋房子是红色、蓝色绿色的最小花费。因此我们可以假设状态：f\[i\]\[0\],f\[i\]\[1\],f\[i\]\[2\]分别记录油漆前i栋房子并且房子i-1是红色、蓝色、绿色的最小花费。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 3、转移方程 ###

设油漆前i栋房子并且房子i-1是红色、蓝色、绿色的最花费分别为

f\[i\]\[0\],f\[i\]\[1\],f\[i\]\[2\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 2]

### 4、初始条件和边界情况 ###

**初始条件**：f\[0\]\[0\]=f\[0\]\[1\]=f\[0\]\[2\]=0表示不油漆任何房子的花费。

### 5、计算顺序 ###

逐行计算，答案是min\{f\[N\]\[0\],f\[N\]\[1\],f\[N\]\[2\]\}

时间复杂度是O(N)，空间复杂度是O(N)

### 6、具体代码实现 ###

class Solution(object):
        def minCost(self, costs):
            """ :type costs: List[List[int]] :rtype: int """
            if len(costs) == 0:
                return 0
            dp = [[0] * 3 for i in range(len(costs))]
            for i in range(3):
                dp[0][i] = costs[0][i]
            for i in range(1, len(costs)):
                for j in range(3):
                    d = j + 1
                    e = j + 2
                    dp[i][j] = min(dp[i - 1][d % 3] + costs[i][j], costs[i][j] + dp[i - 1][e % 3])
            return min(dp[len(costs) - 1][0], dp[len(costs) - 1][1], dp[len(costs) - 1][2])

###  ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/abbe8ced8ae04011984519492442dd98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]: /images/20221024/f9160c5142454c2a937e6734ac61c225.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 2]: /images/20221024/95667a806c1b487c94c114335ad5ea4b.png