Consider a computer game with a $2$D map with axes A$($A$\_(1),$A$\_(2),$dots,A$\_($n$))$ and B$($B$\_(1),$B$\_(2),$dots,B$\_($m$)).$ The

goal is to start from A$\_(1)$B$\_(1)$ and arrive at A$\_($n$)$B$\_($m$)$ by moving one step at a time. At each coordinate

you arrive, you gain a $($positive$)$ number of game points. You have to reach C coins at the end

of the game $($your total score should be C$,$ not less or not more$).$ Additionally, there is a rule

that constricts your movement. If you are at A$\_($i$)$B$\_($j$),$ your next move should be either A$\_($i$)$B$\_($j$+1)$ or

A$\_($i$+1)$B$\_($j$),$ no other.

Example of the game map and proper gameplay: Gameplay example $(1)$:

Route: $,$A$\_(1)$B$\_(1)->$A$\_(1)$B$\_(2)->$A$\_(2)$B$\_(2)->$A$\_(2)$B$\_(3)->$dots$->$A$\_($n$)$B$\_($m$)$

Points: $25+30+15+11+$dots$+12=$C

Gameplay example $(2)$:

Route: $,$A$\_(1)$B$\_(1)->$A$\_(1)$B$\_(2)->$A$\_(2)$B$\_(2)->$A$\_(3)$B$\_(2)->$dots$->$A$\_($n$)$B$\_($m$)$

Points: $25+30+15+88+$dots$+12=$C

Problem: To find the number of possible routes to reach exactly $$ points at the end of the game

$($a$)$ Construct an algorithm $($which is not a DP algorithm$)$ to solve the problem and write down the pseudo$-$code.

$($b$)$ Analyze the time complexity of your algorithm.

$($c$)$ Without using DP$,$ how does $$ affects the running time of the algorithm?

$($d$)$ Design a DP algorithm to solve the problem.

$($e$)$ Is it necessary to use DP$,$ if the problem asks for the maximum number of points, instead of exactly $$ points?

when you are asked to design a dynamic programming algorithm, you should answer the following questions.

$($i$)$ What are the sequence decision steps?

$($ii$)$ What are the alternatives at each decision step?

$($iii$)$ Describe the subproblems.

$($iv$)$ Write the recurrence relation. Explain why it is correct.

$($v$)$ Describe the table that is necessary for the dynamic programming algorithm.

$($vi$)$ Describe how to fill the table.

$($vii$)$ Write down the pseudo$-$code of the dynamic programming algorithm to fill the table.

$($viii$)$ Analyze the running time efficiency of your algorithm.

$($ix$)$ Analyze the space efficiency.

$($x$)$ Write down the pseudo$-$code of an algorithm to find the actual solution for the problem