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)$.
