There are m towns in a straight line, with a road joining each pair of consecutive towns.

There are m towns in a straight line, with a road joining each pair of consecutive towns.

Legends say that an ordinary person in one of these towns will become a hero by completing a sequence of n quests. The first quest will be completed in their home town, but after each quest they may complete their next quest either in the same town or after moving to a neighbouring town.
For example, if n = 5 and m = 4, a resident of town 2 may become a hero as follows:
? begin in town 2 for quest 1,
? then move to town 3 for quest 2,
? stay in town 3 for quest 3,
? return to town 2 for quest 4, and
? move to town 1 for quest 5.
Design an algorithm which runs in O(nm) time and finds the total number of ways
to complete n quests.

Actually, given information Legends say that an ordinary person in one of these towns will become a hero by completing a sequence of n quests. The first quest will be completed in their home town, but after each quest they may complete their next quest either in the same town or after moving to a neighbouring town.
For example, if n = 5 and m = 4, a resident of town 2 may become a hero as follows:
? begin in town 2 for quest 1,
? then move to town 3 for quest 2,
? stay in town 3 for quest 3,
? return to town 2 for quest 4, and
? move to town 1 for quest 5.

This can be solved using dynamic programming approach:

Let i be the town index from where we start our quest and j be no of quests we have to move

then we can define it as

T[i][j] = T[i-1][j-1] + T[i][j-1] + T[i+1][j-1]

T[0][j] = T[1][j-1] + T[0][j-1]

T[n-1][j] = T[n-1][j-1] + T[n-2][j-1]

Pseudo code:

for(i=0;i

for(j=0;j

if(j==0) T[i][j] = 1;

else {

T[i][j] = T[i][j-1];

if(i+1 < n) T[i][j]+= T[i+1][j-1]

if(i-1 >= 0) T[i][j] += T[i-1][j-1]

print maximum value in column m-1 i.e max of T[i][m-1] for all i in [0,n-1] is the answer.

complexity is o(n*m)