
Let each permutation be an edge, an the vertex is its prefix and suffix.
For example, for N = 4 1234 > edge from 123 to 234 1243 > edge from 124 to 243
It is clear that the result is minimum number of edges needed to add, such that there is Euler path in the graph. However, the added edge is weighted, according to number of matching suffix/prefix of the vertex.
All permutations of size N will transform to a graph with N! edges, with (N1)! cycle, each of size N. Hence, the problem is to "connect" the cycles.
// Here is my probably wrong assumption. If we consider only edges with weight 1, the problem to connect the cycles is identical to the original problem of size N1, hence the recurrence relation. You can check it by drawing for small N. So this technique may be wrong if we need to use edges with weight > 1. 