There are a row of?n?houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a?n?x?3?cost matrix. For example,?costs[0][0]?is the cost of painting house 0 with color red;?costs[1][2]?is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
1 用動(dòng)態(tài)規(guī)劃來實(shí)現(xiàn)驱入，如果dp[i][j]表示給第i+1個(gè)房子刷顏色j裂逐，則上一個(gè)房子肯定是刷顏色j+1或者是j+2，即dp[i-1][j+1]或者dp[i-1][j+2]石咬，所以dp[i][j]=min(dp[i-1][j+1], dp[i-1][j+2])+dp[i][j]
2 注意當(dāng)涂第i+1個(gè)房子的時(shí)候猾昆，會(huì)有三種選擇豺型，基于這三種選擇中的任何一個(gè)奋蔚，前面都有涂另外兩種顏色的最小cost娘汞。比如當(dāng)前房子想涂紅色，那當(dāng)前房子涂紅色的最小cost=min（pre涂藍(lán)色最小cost先匪，pre涂綠色最小cost）+ 當(dāng)前涂紅色cost
3 也就是說對(duì)于第一所房子來說种吸，我們有三種選擇，將有三種cost呀非，到第二所房子的時(shí)候坚俗，我們也會(huì)有三種選擇：
? ? 第二所涂紅色，cost = min（第一所涂藍(lán)色cost岸裙，第一所涂綠色cost）+ 第二所涂紅色cost
? ??第二所涂藍(lán)色猖败，cost = min（第一所涂紅色cost，第一所涂綠色cost）+ 第二所涂藍(lán)色cost
? ??第二所涂綠色降允，cost = min（第一所涂紅色cost恩闻，第一所涂藍(lán)色cost）+ 第二所涂綠色cost
4 依次下去，到最后一所房子的時(shí)候剧董，有三種選擇幢尚，然后有三個(gè)cost，選擇最小cost的那個(gè)顏色
5?pre = costs[0][:]是指把costs的第一排的值全部復(fù)制到pre中
6?now =[0]*3代表初始化一個(gè)list送滞，[0,0,0]
7 更新的時(shí)候侠草，一個(gè)一個(gè)更新now[0], now[1], now[2]
必須要有tmp變量
1? 思路是對(duì)于當(dāng)前house，paint紅色的話犁嗅，那就從上一個(gè)房子噴藍(lán)色和綠色中選cost小的那個(gè)方案边涕，然后加上當(dāng)前cost；同理褂微，paint藍(lán)色的話功蜓，就從上一個(gè)房子噴紅色和綠色中選cost小的那個(gè)方案，然后加上當(dāng)前cost宠蚂；......
2 所以對(duì)于當(dāng)前房子式撼，噴紅色，藍(lán)色和綠色求厕，分別有各自的最小cost的方案組合著隆，就這樣一直更新扰楼，直到最后一個(gè)房子，在紅色美浦，藍(lán)色和綠色三種方案中再找到最小cost那個(gè)方案就是所得
