Please help me on how to approach this problem with O(nk)

#1

https://www.lintcode.com/problem/paint-house-ii/description