First of all we may notice that we don't have to consider moves where some of the feet end on the position Zero.
Why is this the case? Suppose the contrary – that in each optimal solution the dancer had to land some of his feet on the position Zero. Take any optimal solution where this happens the least number of times. Let's take a look at the first moment when some of his feet landed on Zero. If these feet are never used again, he could put them on numbered positions instead. Otherwise consider the first moment when one of them is used, i.e. moved to some other position. But clearly the dancer could have moved it there sooner instead of moving it to Zero. This leads to a contradiction. (In other words, using the approach above we can convert any optimal solution to an optimal solution where Zero is never used.
We should also decide how to encode the moves and states of the dancer. The most appealing form is certainly the binary one – we will use A-bit numbers to store bit vectors. If the dancer has (or is supposed to have) a foot on some position, the corresponding bit in the number will be one, otherwise it will be 0. E.g. the state 1100 would mean that the dancer has feet on positions 3 and 4. Similarly, the move 1001 would mean that the dancer has to stamp on positions 1 and 4. One more definition: the distance between two states is the number of feet that need to be changed. In our encoding the distance can be computed easily (it is simply one half of the number of ones in the bitwise xor of the states).
Now back to the main problem. We will use dynamic programming. We will have a 2D-array A telling us the maximum number of moves we can catch for the given second and the given state of the dancer.
In the 0th second we certainly cannot catch any move, so we will fill the first row of the array with zeros. Now assume that for a given k we know the maximum number of moves we can catch for all of the seconds i where i < k and all of the dancer states in that seconds. Now suppose that we want to compute the results in the k-th second for the state l: A[k][l]. For each possible state j of the dancer we compute the distance from j to l and thus the time tj it takes to jump from j to l. If before catching the current move the dancer was in the state j, the maximum number of moves he could catch so far is A[k-tj][j]. Note that we have already computed this number.
We need to handle a few special cases. If the time at position j is negative (i.e. k < tj), the dancer couldn't be in the given position, so we may ignore this possibility. If there is required move to perform in the second k and by moving to state l the dancer catches this move, we add 1 to the currently computed best number of moves. Don't forget about the case when the dancer stood still for one second (but note that in this case he doesn't catch the move, even if his feet are on correct positions).
The result is the maximum in the last row of the computed table.
There is one slight optimization: we don't have to call a function to compute the distance between two states every time we need it, because that is quite time consuming. Therefore we should precompute its values into the 2D-array D (so that D[i][j]=distance(i, j)).