The answer given is incorrect. The number of moves required to solve the puzzle should be this sequence, given by $(n^2+n-2)/2$ (where $n=\#\text{ of frogs}$).
Let's write the formation of the frogs as a string of numbers $ 0$ through $ n$, denoting the empty space by $ 0$. With this notation, we can see that each turn is defined by swapping the $ 0$ with the number one or two spaces to the left or right, corresponding to a frog on the left or right hopping or leaping to the right or left, respectively. Since we'll be focusing on the $ 0$, it will be easiest to say that the $ 0$ is leaping to the left when a frog is leaping to the right, and analagously for the other cases.
Now, for aesthetics, we can consider the formations as vertices of a layered tree, each layer of the tree corresponding to a turn of the frog moving game. We put a directed edge from formation $ a$ (in layer $ i$) to formation $ b$ (in layer $ i+1$) if a legal move takes us from $ a$ to $ b$. Viewed in this way we can consider the puzzle as a shortest path problem from $ 0123\ldots n$ to $ n\ldots 3210$ (or to $ n\ldots 3201$, $ n\ldots 3021$, $ n\ldots 0321$, etc). Since we are interested only in shortest paths, the layers of the tree will be disjoint, as moving to an in-neighbor would imply we could have gotten there in fewer moves.
The Even Case.
I find the even case a bit easier to visualize, so let's start with that. Here is what the puzzle looks like with $ 4$ frogs.
You can see there are several solutions, highlighted in red, with the shortest one bolded. Let's zoom into these paths and walk through them.
Every solution follows the same pattern. First, the $ 0$ is moved all the way to the right, then reverses direction. We don't want to undo our previous move, so there is only one one available option - if we leaped right, we need to hop left, and vice versa. When we get $ 0$ back to the leftmost position, we reverse direction again. This process repeats until all the numbers are in order. (See: "Why does this work?") The fastest way to do this is highlighted in the red path - every move to the right is a leap, and there are exactly two hops to the left.
If we say that moving $ 0$ all the way to the right, then all the way back to the left constitutes a "round," then each round takes $ n/2$ leaps to the right + $ 1$ hop to the left + $ (n-2)/2$ leaps to the left + $ 1$ hop to the left. That's $ n+1$ total moves, $ 2$ hops and $ n-1$ leaps. Since each round moves the biggest number to the left twice and the smallest number to the right twice, we only need to do this $ n/2$ times to get everything in order. Also, we can skip the last step (which would only serve to put $0$ on the far left), so the even case requires $$ \frac{n(n+1)}{2}-1 =\frac{n^2+n-2}{2} \text{ moves}$$ with $$\frac{n(n-1)}{2}\text{ leaps}$$ and thus $$n-1\text{ hops.}$$
The Odd Case.
For $5$-frogs, the full diagram is too big, but we can look at its solutions.
Here is where we diverge from the answer given. We can do it in $ 14$ moves, $ 2$ less than $ (5^2+3\times 5)/2-4=16$.
We use essentially the same strategy here as in the even solutions. Let's write out the algorithm explicitly. The starting formation is $ 0123\ldots n$ and the starting direction is $ d=1$. Every turn, check first if $ 0$ is at position $ 1$ or $ n-1$. If it's at position $ p_0= 1$, let the $ 0$ hop left to position $ 0$ and set $ d=1$. If it's at position $ p_0= n-1$, have the $ 0$ hop right to position $ n$ and set $ d=-1$. In any other position $p_0$, the $ 0$ leaps to position $ p_0+2d$. We continue in this manner until the frogs are in the formation $ n\ldots 3201$.
Again we can see that each round has $n+1$ moves, $n-1$ leaps and $2$ hops (now in opposite directions). After completing $ k$ rounds, there are $ 2k-1$ numbers to the right of $ n$. If we do this $ (n-1)/2$ times, we have $ n-2$ numbers to the right of $ n$. In this situation, we only need to complete a 'half round' to finish - that is, once we get $ 0$ back to position $ n-1$, everything will be complete. That's $ (n-1)/2$ leaps, so we have a total of $$\left(\frac{n-1}{2}\right)(n+1)+\frac{n-1}{2}=\frac{n^2+n-2}{2} \text{ moves, }$$
which breaks down to
$$\left(\frac{n-1}{2}\right)(n-1)+\frac{n-1}{2}=\frac{n(n-1)}{2} \text{ leaps }$$
and
$$2\left(\frac{n-1}{2}\right)=n-1 \text{ hops.}$$
Why does this work?
Luckily we can understand our solution using some permutation theory. Let's prove it works for the odd case. Taking $0$ from left to right induces the permutation $$(0,n,n-1,n-3,n-5,n-7,\ldots,8,6,4,2)$$ in $\text{Sym}(\{0,\ldots,n\})$. Taking it from right to left induces the permutation $$(0,1,3,5,7,9,\ldots,n-4,n-2,n).$$ Multiplying these permutations, we get $$\sigma:=(1, 3, 5, 7, 9, 11,\ldots, n,n-1,\ldots,10,8,6, 4, 2).$$ So if we let $\sigma=(\sigma_1,\ldots,\sigma_{n})$, then we have that $$\sigma_k=\left\{\begin{array}{lcl}2k-1&:&k=1,\ldots,\frac{n+1}{2}\\ 2 (n - k + 1) &:&k=\frac{n+1}{2}+1,\ldots,n\end{array}\right.$$ where the indices are taken mod $n$.
Let $m=(n-1)/2$. We have, in general, that in cycle notation we can write $$(i_1,i_2,i_3,\ldots,i_c)^{m}=(i_{1+m},i_{1+2m},i_{1+2m},\ldots,i_{1+cm}),$$ where the indices are taken modulo $c$. From this we obtain
$$\begin{eqnarray*}\sigma^{m}&=&(1, 3, 5, 7, \ldots, 2m+1,2m,\ldots,8,6, 4, 2)^{m}\\&=&(2,n-2,4,n-4,\ldots,m+1,m,\ldots,3,n-1,1,n).\end{eqnarray*}$$
Applying this permutation to $0,\ldots,n$ yields the formation $$0,n-1,n,n-3,n-2,n-4,n-3,\ldots,5,2,3,1.$$ So now, we can see that we just need to leap $n$ to the left, then $n-2$, then $n-3$, etc. until we reach $n,n-1,n-2,\ldots,3,2,0,1$.
The even case is proven identically.
How do we know this is the smallest possible number?
Every move can at most reverse the order of $2$ frogs. We must put frog $n$ to the left of all $n-1$ of the other frogs, so that is at least $n$ leaps right there. This does not modify the order of the other frogs, so to move frog $n-1$ to be to the left of the $n-2$ remaining frogs, we will need at least $n-2$ leaps. Continuing in this fashion, we need at minimum $$\sum_{k=1}^{n-1}k=\frac{n(n-1)}{2}$$ leaps. However, discussed above, we need $1$ hop each for frogs $2$ to $n$ to change direction, so we need at least $$\frac{n(n-1)}{2}+n-1=\frac{n^2+n-2}{2}$$ moves. Thus our construction is of minimal length.
The strategy I employ is simply to make the move that leaves the most available moves, and to disregard score entirely. As a natural consequence of playing more moves, the score of the board will increase simply because the only way to continue playing is to make combinations, and combinations generate higher scores.
At the beginning of the game, the most important thing to consider is the placement of $1$s and $2$s. They are unique in that nothing can be combined adjacent to them to make a valid combination, they will only combine with their complement, which can only be achieved by board translation (verses, say a
$12$, which can be adjacent to a $6$, which combines with another $6$ and then the $12$ can subsequently combine with that $12$. There's no way to make a $1$ or a $2$, it must simply be moved around the board).
Later, with higher scoring tiles on the board, the "bonus" tile (which shows up as a white tile with a $+$ in it at the top) becomes increasingly important, and the best strategy I've found is to attempt to place the bonus tile as near a mixed group of larger tiles as possible. The bonus tile will always be at least $6$, but never the same score as your highest scoring tile in play.
There is also the nature of the tile selection. It's been reverse engineered that the random generator uses a "bag" where $12$ tiles are shuffled. The original board layout uses this method, and $9$ tiles are placed into the board with $3$ remaining in the "bag". Once the bag is exhausted, the tiles are shuffled again. There are always $4$ of each: $1$, $2$, and $3$. Once you reach a high tile of $48$ a "bonus" tile is inserted with a potential value of greater than $3$. This changes the size of the "bag" to $13$ instead of $12$. So, keeping track of where you are in the "bag" and how many of each color you've seen can give you an advantage when looking at future moves.
Curiously, the possibility space for scoring is actually quite sparse. All scores will necessarily be multiples of $3$, but it turns out that only about $\frac38$ of the multiples of $3$ between $0$ and the max score are actually valid. There are a lot that are simply impossible to get, like a $19$ in cribbage.
The lowest one that isn't trivially small is still $39,363$, though, which seems well out of the range of the average player. The next lowest I found is $52,485$. There are lots of gaps at the high end, due to the fact that highest scoring tile is worth over $500$k by itself.
Best Answer
I have been unable to come up with anything resembling a formal proof, but I have noticed several things that may help someone do so.
Therefore, let $a$ denote moving the only moveable frog of color $A$ (moving to the right), and let $b$ denote moving the only moveable frog of color $B$ (moving to the left).
If, at any point, two frogs of the same color are in adjacent positions, there is a frog of the other color ahead of them, and the open lilypad is behind them, you have lost.
Using this, it's impossible to ever move $aa$ (if there is a $B$ frog to the right), unless one of the $A$ frogs jumps a $B$ frog.
Extending this, if you have moved $k$ of your $A$-colored frogs, there are at most $k$ jumps possible for the $B$ frogs, and you cannot make more than $(k+1)$ $b$-type moves consecutively.
Stepping through the game case by case, it's pretty easy to manually show that there's one possible choice for the next sequence of moves. (I have no proof for this, but I have not yet found a counterexample).
You get the idea by now, but it shouldn't be too difficult to write an automated prover for small $m$ and $n$.