• Leetcode 3429. Paint House IV
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3429. Paint House IV

1. 解题思路

这一题解法上就是一个动态规划的思路，由于题目有两个限制条件，即相邻不可以同色，以及前后同位置不可以同色，因此我们在迭代的时候需要从首尾同步考虑两两的配色组合，剩下的就是简单的动态规划遍历所有可能性即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minCost(self, n: int, cost: List[List[int]]) -> int:@lru_cache(None)def dp(idx, prefix, suffix):if idx == n // 2:return 0i, j = idx, n-1-idxans = math.inffor c1 in range(3):for c2 in range(3):if c1 == c2 or c1 == prefix or c2 == suffix:continueans = min(ans, cost[i][c1] + cost[j][c2] + dp(idx+1, c1, c2))return ansreturn dp(0, -1, -1)

提交代码评测得到：耗时2108ms，占用内存143MB。