There are m towns in a straight line, with a road joining each pair of consecutive towns. Legends say that an ordinary p

[answerhappygod]

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.
Clarifications:
• What input is provided in an instance of the problem? The
input consists only of n and m, the number of quests and the number
of towns.
• Does the hero have to start in any particular home town? No.
You should calculate the sum over all starting towns.
• Does order matter in a path? Yes. Completing quests in towns 1
→ 1 → 2 is a different path to 1 → 2 → 1.
Hint: Is the single parameter “number of quests completed”
sufficient to define the subproblems? If not, why not, and what
other parameter(s) are required?
Do not write the code, give steps and methods. Explain
the steps of algorithm, and the logic behind these steps in plain
English and give Diagrams and time complexity