1.题目1.题目描述剑指OfferII091.画房子难度：中如果有一排房子，一共n个，每个房子可以涂红色、蓝色或绿色三种颜色中的一种，你需要把所有的房子都涂上，让相邻的两间房子颜色不同。当然，由于市场上不同颜色的油漆价格不同，所以粉刷不同颜色的房子的成本也是不同的。将每栋房子粉刷成不同颜色的成本由nx3正整数矩阵成本表示。例如costs0代表0号房子刷成红色的费用；costs1代表粉刷1号房绿化的费用，以此类推。请计算粉刷所有房屋的最低成本。示例1：输入：costs=[[17,2,17],[16,16,5],[14,3,19]]输出：10解释：油漆房子0蓝色，油漆房子1油漆绿色和门牌号2漆成蓝色。最小成本：2+5+3=10。示例2：输入：costs=[[7,6,2]]输出：2提示：costs.length==ncosts[i].length==31<=n<=1001<=costssi<=20注：本题与主站256题相同：https://leetcode-cn.com/probl...2.原题链接：剑指OfferII091。Paintthehouse2.解题报告1.思路分析比较简单的DP。我们让dp[i]j是当第i个房子被涂成三种颜色时前i个房子的总成本。显然答案是min(dp[n-1])。那么，当第i栋房子涂上颜色0时，那么第i-1栋房子就只能涂上颜色1和2，我们可以从中找出较小的选择，然后计算第i栋房子的成本;当我用颜色1绘画时，我-1只能刷颜色0,2；i刷颜色2，i-1刷颜色0,1，状态转移方程很明显：dpi=costsi+min(dpi-1,dpi-1)dpi=costsi+min(dpi-1,dpi-1)dpi=costsi+min(dpi-1,dpi-1)讨论边界：第0宫显然没有极限，那么dp[0]=cost[0]2。复杂度分析最差时间复杂度O(n)3。代码实现了dp。类解决方案：defminCost(self,costs:List[List[int]])->int:n=len(costs)dp=[[0]*3for_inrange(n)]dp[0]=costs[0]foriinrange(1,n):dp[i][0]=costs[i][0]+min(dp[i-1][1],dp[i-1][2])dp[i][1]=成本[i][1]+min(dp[i-1][0],dp[i-1][2])dp[i][2]=成本[i][2]+min(dp[i-1][1],dp[i-1][0])returnmin(dp[n-1])3.本题小结1）只设计状态转换.人生苦短，我用Python！
