s***f
发帖数: 226 | 1 There are a row of houses, each house can be painted with three colors red,
blue and 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. You have to paint the houses with minimum cost. How
would you do it? | r*********g
发帖数: 67 | | o***g
发帖数: 2784 | 3 假设前面N个已经刷好了，第N+1个，不能和第N个同颜色，就剩俩颜色了，选便宜的那个
第一个就三个里面选最便宜的。
,
houses
【在 s***f 的大作中提到】
: There are a row of houses, each house can be painted with three colors red,
: blue and 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. You have to paint the houses with minimum cost. How
: would you do it?
| g*********e
发帖数: 14401 | 4 minCost(first i houses, i th house with color x)
,
houses
【在 s***f 的大作中提到】
: There are a row of houses, each house can be painted with three colors red,
: blue and 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. You have to paint the houses with minimum cost. How
: would you do it?
| o***g
发帖数: 2784 | 5 这个还真有问题，比如
R G B
1 10 100 1000
2 1 1000 10000
第一个选了10，第二个就得选1000，结果是1010
其实答案应该是第一个选100，第二个选1，结果是101
那个
【在 o***g 的大作中提到】
: 假设前面N个已经刷好了，第N+1个，不能和第N个同颜色，就剩俩颜色了，选便宜的那个
: 第一个就三个里面选最便宜的。
:
: ,
: houses
| R******9
发帖数: 267 | 6 use a 3*N matrix.
fun('R', i) = cost('R', i) + min(fun('B', i-1), fun('G', i-1));
fun('G', i) = cost('G',i) + min(fun('R', i-1), fun('B', i-1));
fun('B', i) = cost('B', i) + min(fun('R',i-1), fun('G', i-1));
【在 o***g 的大作中提到】
: 这个还真有问题，比如
: R G B
: 1 10 100 1000
: 2 1 1000 10000
: 第一个选了10，第二个就得选1000，结果是1010
: 其实答案应该是第一个选100，第二个选1，结果是101
:
: 那个
|
|
