# Maximize points of K dance moves

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

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\times 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(NK^2)$ or $O(KN^2)$ solution (don't quite remember if it's one or the other).

How do I get that solution or what's the best solution to this problem?

Thanks!

We can model the transition of one move to another using the following discrete dynamics:

\begin{align} m_{n+1} &= u_{n} \end{align}

where $m_{n}$ is the $n^{th}$ move you performed and $u_{n}$ is the $n^{th}$ choice of the next move you will make. Note that both $m_n$ and $u_n$ are members of the move set, $\mathcal{M}$. The cost function you wish to maximize might then be of the form:

\begin{align} V &= P_{M}(m_{K+1}) + \sum_{j=1}^{K} P_{M}(m_j) + P_{T}(m_j,u_j) \end{align}

where $P_{M}(\cdot)$ gives you points for your current move and $P_{T}(\cdot, \cdot)$ gives you points from the transition from $m_j$ to $u_j$. Given this formulation, you can then recursively find an optimal policy, $\mu^{*}_{j}(m)$, that will generate optimal sequences given some move at step $n$ of the sequence. This can be found via:

\begin{align} V^{*}_{K+1}(m) &= P_{M}(m) \; \forall m \in \mathcal{M} \\ V^{*}_{j}(m) &= \max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \mu^{*}_{j}(m) &= \arg\max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \end{align}

Once you have found the optimal policy $\mu^{*}_{j}(m)$, you can obtain an optimal dance move sequence from some dummy starting move using the following:

\begin{align} m_{n+1} &= \mu^{*}_{n}(m_{n}) \end{align}

In this case, $\lbrace m_2, m_3, \cdots, m_{K+1}\rbrace$ would be your optimal set of $K$ moves. Now as we can tell from the recursive algorithm, we would essentially have three nested loops to obtain the optimal policy. These nested loops together are $O(KN^2)$ because we loop through all $m$ and $u$ (both of size $\left| \mathcal{M}\right| = N$) at a given step for $K$ steps. Generating the optimal sequence is then just $K$ steps, but the recursive algorithm is the dominant part of the algorithm computationally.

Simplified Explanation

So in the explanation above, we defined the dynamics to obtain the next move $m_{n+1}$ based on information we know, like the current move $m_n$ and the choice of what move to make next, $u_n$. We also defined a cost function to maximize, $V$.

To solve this problem using Dynamic Programming, we treat the cost function as a reward for a discrete trajectory and try to find optimal sub-trajectories, starting from the end of the sequence. The logic behind this is we can incrementally solve the optimal trajectory by using previously found optimal sub-trajectories.

We can define the final cost trajectory term as:

\begin{align} V^{*}_{K+1}(m_{K+1}) &= P_{M}(m_{K+1}) \end{align}

where $m_{K+1}$ is within the set of moves, $\mathcal{M}$. We can define this term because it is independent of the decision variable, $u$, which is what we are trying to find an optimal algorithmic strategy to choose. Now the recursive relationship for the next piece of the cost trajectory is:

\begin{align} V_{K}(m_K, u) &= P_{M}(m_K) + P_{T}(m_K, u) + V^{*}_{K+1}(m_{K+1}) \end{align}

where $u$ can be any move within $\mathcal{M}$. Note how this equation depends on the value for $m_{K+1}$. This dependence is where you incorporate your knowledge of the dynamics. We know based on the discrete dynamics that this cost term can be redefined as:

\begin{align} V_{K}(m_K, u) &= P_{M}(m_K) + P_{T}(m_K, u) + V^{*}_{K+1}(u) \end{align}

Our goal now is to find the optimal value of $V_{K}(m_K)$, for each value of $m_K$ within $\mathcal{M}$, with respect to $u$. This is simply written as:

\begin{align} V^{*}_{K}(m_K) &= \min_{u \in \mathcal{M}} V_{K}(m_K, u) \end{align}

Note that we also define the optimal value of $u$ for a given step $j$ and a given state $m$ as the optimal policy $\mu^{*}_j(m)$. We can use the above findings to thus define a recursive formulation to find the optimal cost:

\begin{align} V^{*}_{K+1}(m) &= P_{M}(m) \; \forall m \in \mathcal{M} \\ V^{*}_{j}(m) &= \max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \mu^{*}_{j}(m) &= \arg\max_{u \in \mathcal{M}} P_{M}(m) + P_{T}(m,u) + V^{*}_{j+1}(u) \; \forall m \in \mathcal{M}, \forall j \in \lbrace 1, 2, \cdots, K\rbrace \\ \end{align}

Note that $j$ should start at $K$ and be decremented down to $1$. Implementing this algorithm becomes a series of nested loops. This can be shown in pseudo-code to be the following:

for m in {Set of Moves}
V_opt(K+1,m) = P_m(m)
end

for j going from K to 1, increment -1
for m in {Set of Moves}
// initialize V_opt(j,m)
V_opt(j,m) = -Infinity

for u in {Set of Moves}
points = P_m(m) + P_t(m,u) + V_opt(j+1,u)
if( V_opt(j,m) < points )
V_opt(j,m) = points
policy_opt(j,m) = u
end
end // end for loop u
end // end for loop m
end // end for loop j


After finding the optimal policy $\mu^{*}_j(m)$ (policy_opt(j,m) in code), you can generate the optimal moves using the dynamics as noted previously. As you can see looking at the pseudo-code, the algorithm uses 3 nested loops, two of size $N$ and one of size $K$. This makes the problem dominated by a computational complexity of $O(KN^2)$.

• Sorry, I've read the solution multiple times and it seems like it's just way over my head. Don't think math is my strong suit. Could you explain it simpler (perhaps with code)? Or could you recommend resources to help me build the skill to be able to solve these kind of problems? – Waley Chen Mar 7 '17 at 20:24
• @WaleyChen No worries. I can try to write it in psuedo-code/code later in terms of for loops, it isn't as complicated as it appears, I promise. A book I recommend for Dynamic Programming is Dynamic Programming and Optimal Control by Bertsekas. You could just get Volume I to get up to speed (try checking his site to see if he has a free PDF of it). – spektr Mar 7 '17 at 20:36
• @WaleyChen I have added a second part to my answer which should hopefully be simpler to understand, especially since there is some pseudo-code. – spektr Mar 8 '17 at 15:29