paint-house-iii

1473. 给房子涂色 III

思路

根据Hard必死定律，再加上周赛dp必死定律。这道题依旧是没有做出来。但是这次做完了阅读理解，也尝试着在纸上构造了一下转态转移，也算是小有进步吧。
阅读大佬解法，获得新思路：

• 动态规划我们首先要找出状态，状态之前满足最优子问题和后无效性，确定状态转移方程，然后开始求解
• 这道题中，分析状态，主要有三个：房子、颜色、街区
• 构造dp数组 dp[k][i][j] 代表涂到第k个房子，使用颜色i，街区数量-1为j时的最小花费（使用街区数量-1，方便从下标0开始进行状态转移）
• 遍历房子进行涂色，当前房子涂成什么颜色，是根据前边的房子来的。所以将涂到第几个房子作为第一维度。
• 假设0个房子有颜色1，dp[0][1][0] = 0; dp[0][other][0] = math.inf ，表示第0个房子已经涂了颜色了，不需要再涂，所以花费为0。其他的颜色无法再涂，花费为无穷大
• 状态转移

1.当前房子有颜色
    1.dp[k][i][j] = dp[k-1][i][j] （颜色相同，街区不加，且当前房子有颜色费用为0）
    2.dp[k][i][j] = dp[k-1][!=i][j-1] （颜色不同，街区加1，当前房子有颜色，不用刷，当前费用为0）
2.当前房子没有颜色
    1.dp[k][i][j] = dp[k-1][i][j] + cost[k][i] （颜色相同，街区不加，加上刷当前的房子的费用）
    2.dp[k][i][j] = dp[k-1][!=i][j-1] + cost[k][i]（颜色不同，街区加1，加上刷当前的房子的费用）

以上，尝试写一下代码。