w**n
发帖数: 122 | 1 就是前面某位拿了一堆Offer的大牛贴的
minimize the cost of painting K houses, each house has different
costs to paint in different colors,
2 houses (next to each other) cannot be painted in the same
color. DP 问题
请教怎么DP?
谢谢先!! |
f*********d
发帖数: 140 | 2 只想出一个复杂度KC^2的dp
不知道KC可解否
K:#of house
C:#of colors
【在 w**n 的大作中提到】
: 就是前面某位拿了一堆Offer的大牛贴的
: minimize the cost of painting K houses, each house has different
: costs to paint in different colors,
: 2 houses (next to each other) cannot be painted in the same
: color. DP 问题
: 请教怎么DP?
: 谢谢先!!
|
f*********d
发帖数: 140 | 3 可以优化到KClogC
还是不知道KC可解否~
【在 f*********d 的大作中提到】
: 只想出一个复杂度KC^2的dp
: 不知道KC可解否
: K:#of house
: C:#of colors
|
f*********d
发帖数: 140 | 4 嗯 O(KC)可解~
【在 f*********d 的大作中提到】
: 可以优化到KClogC
: 还是不知道KC可解否~
|
f*********d
发帖数: 140 | 5 dp[k][c]: the optimal solution of painting the first k houses where the
kth house is colored with color c.
dp[k-1][1, C] => dp[k][1, C] transition cost can be reduce to O(C)
【在 w**n 的大作中提到】
: 就是前面某位拿了一堆Offer的大牛贴的
: minimize the cost of painting K houses, each house has different
: costs to paint in different colors,
: 2 houses (next to each other) cannot be painted in the same
: color. DP 问题
: 请教怎么DP?
: 谢谢先!!
|
w**n
发帖数: 122 | 6 没太看懂
如果 dp[k-1][c] 是 paint K-1个house的最优解（cost最低），并且第k-1个house是
用颜色C
那么dp[k][x]里， x必须是跟C不一样的颜色。如果取颜色X, min(cost(x)) x!=C, 这
个不一定是k个house的最优解8
【在 f*********d 的大作中提到】
: dp[k][c]: the optimal solution of painting the first k houses where the
: kth house is colored with color c.
: dp[k-1][1, C] => dp[k][1, C] transition cost can be reduce to O(C)
|
f*********d
发帖数: 140 | 7 找到dp[k-1][1..C]里面最小的一个，并且计数, 如果最小的计数个数>1 ，那么，等不
等于C就无所谓了，如果最小的计数个数=1， 再记录一个次小的即可~
错了请指出~
【在 w**n 的大作中提到】
: 没太看懂
: 如果 dp[k-1][c] 是 paint K-1个house的最优解（cost最低），并且第k-1个house是
: 用颜色C
: 那么dp[k][x]里， x必须是跟C不一样的颜色。如果取颜色X, min(cost(x)) x!=C, 这
: 个不一定是k个house的最优解8
|
