How to formulate this as a DP problem?
Problem Statement:
Find the number of ways to pick the element from the array which are not visited.
We starting from 1,2,.....,n with some (1<= x <= n) number of elements already picked/visited randomly which is given in the input.
Now, we need to find the number of ways we can pick rest of the (n - x) number of elements present in the array, and the way we pick an element is defined as:
On every turn, we can only pick the element which is adjacent(either left or right) to some visited element i.e in an array of elements:
1,2,3,4,5,6 let's say we have visited 3 & 6 then we can now pick 2 or 4 or 5, as they are unvisited and adjacent to visited nodes, now say we pick 2, so now we can pick 1 or 4 or 5 and continues.
Example:
input: N = 6(number of elements: 1, 2, 3, 4, 5, 6)
M = 2(number of visited elements)
visited elements are = 1, 5
Output: 16(number of ways we can pick the unvisited elements)
ways: 4, 6, 2, 3
4, 6, 3, 2
4, 2, 3, 6
4, 2, 6, 3
4, 3, 2, 6
4, 3, 6, 2
6, 4, 2, 3
6, 4, 2, 3
6, 2, 3, 4
6, 2, 4, 3
2, 6, 4, 3
2, 6, 3, 4
2, 4, 6, 3
2, 4, 3, 6
2, 3, 4, 6
2, 3, 6, 4.
Think of a string of adjacent unpicked numbers, like 2,3,4 in the example.
At any time you can only pick one of the two ends. So you have two choices each time, until you get to the last one. So if you look at this string alone, there are $2*2*1 = 4$ ways of consuming it.
The same is true of any other string. Trivially, the 6 in the example can only be consumed in $1$ way.
You then have to figure out in how many ways we can order the moves. In this case we must have 3 moves applied to the length 3 string $2,3,4$, and one move applied to the length 1 string $6$. These can be interleaved in $\binom{4}{3} = \frac{4!}{3!1!} = 4$ ways. If you have more than two strings, you need to use the appropriate multinomial instead of the binomial used here.
Finally multiply it all together to get the answer, in this case $(4*1)*4=16$.