Maximize points of K dance moves
We can model the transition of one move to another using the following discrete dynamics:

\begin{align}
m_{n+1} &amp;= 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 &amp;= 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) &amp;= P_{M}(m) \; \forall m \in \mathcal{M} \\
V^{*}_{j}(m) &amp;= \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) &amp;= \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} &amp;= \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}) &amp;= 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) &amp;= 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) &amp;= 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) &amp;= \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) &amp;= P_{M}(m) \; \forall m \in \mathcal{M} \\
V^{*}_{j}(m) &amp;= \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) &amp;= \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) &lt; 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)$.