515.&516. Paint House I&II

I就不提了,记得dp的公式是cost[i][0] += Math.min(cost[i-1][1], cost[i-1][2]) ,是+=哦亲。然后重要的事情说三遍,把y坐标换成1和2再写一遍,最后return的是cost[len-1][0,1,2]的最小值

直接说II,就是I的扩展,需要定义Min,MinSecond和MinIndex,代表“上一轮”的。然后再每层循环里还要有她们的副本,为了是得到以后赋值给他们。say他们叫current系列。想象下,外面三个领导等着每轮的结果,里面三个卖命的current每层循环都要去比较和修改自己。最后去领奖的还是领导,卖命的就一直在循环体里。三个卖命的生命周期是在n循环的里面,k循环的外面。因为他们求的是每一行的min和min和minindex。当然三个领导也不会太闲着,他们也负责指导工作,就是在k的循环里,cost[i][j]是+=Min还是MinSecond这两个领导的值,取决于是否j等于MinIndex。 然后再比较更新cost[i][j]和三个卖命的currentMin,currentMin2和currentMinIndex

还有一点要说明的是,不管是I还是II,cost[i][j]在循环完以后都不再代表第i个涂j号颜色的费用,而是表示涂到第i个用j号颜色的总花费。所以最后都是要在最后一排找最小值,因为最后一排表示所有都涂完的不同策略的情况的消耗。

Show your support

Clapping shows how much you appreciated DeReK’s story.