I am trying to solve problem Uva-10128 (Queue) on UVa Online Judge. I am not able find a way to approach this problem. I searched on internet and found that most of people has solved this problem by precalulating using DP.
DP[1][1][1] = 1;
for(N = 2; N <= 13; N++)
for(P = 1; P <= N; P++)
for(R = 1; R <= N; R++)
DP[N][P][R] = DP[N-1][P][R]*(N-2) + DP[N-1][P-1][R] + DP[N-1][P][R-1];
Above code snippet is taken from https://github.com/morris821028/UVa/blob/master/volume101/10128%20-%20Queue.cpp.
Can someone please explain formula used in above code.
Thanks
When you calculate DP[N][P][R] you look at the position of the smallest person in the queue. Because he is the smallest, he can't block anybody. But he will get blocked if he doesn't stand at either end of the queue.
If he is the first person in the queue he is seen from the beginning of the line. So if we remove him, the queue contains N-1 people and you can only see P-1 people from the beginning, but still R people from the end. Therefore there are DP[N-1][P-1][R] combinations.
If he is in the middle, then by removing him we still can see P and R people. And since there are N-2 positions in the middle, there are DP[N-1][P][R] * (N-2) combinations.
And if he is the last person in the queue we get DP[N-1][P][R-1] combinations. The reasoning is identically to the first case.
So the total number of combinations for DP[N][P][R] is the sum of all three cases.