In this problem, I want to maximize the number of points of K dance moves. There are N possible dance movies.

Each of the dance moves have a point value associated with it which can be positive or negative.

There are also points from transitioning from one dance move to another. We're given an N x N matrix that has the points gained from transitioning from one dance move to another.

The brute force solution is easy which is simply try every dance move for the 1st move, then the 2nd move, then the 3rd ... which is O(N^K).

My interviewer says there's a O(K * N^2) solution.

How would you get the solution?

p.s. I also asked this question here but I'm looking for a solution that's easier to understand:

http://cs.stackexchange.com/questions/71258/maximize-points-of-k-dance-moves

Thanks!