Robots on Grids

Let's consider a robot on an $mxn$ grid of squares $($that is$,m$ rows and $n$ columns$).$ The robot starts in the top$-$left square, and its target is at the bottom$-$right. The robot has two moves available to it $-$ it can move one square to the right, or one square down $-$ so it must make a combination of rightward and downward moves to reach its target. It follows that the robot will take $(m+n-2)$ steps to reach its target.$|$

Here are two such paths it could take:

Your task is to write code that counts the number of possible paths for the robot, given an $m$ and $n.$

Write a function num paths $(m,n)$ that recursively computes the number of paths from the top$-$left to bottom$-$right square of an $mn$ grid without memoization.

Write a function num$\_$paths$\_$memo $(m,n)$ that does the same, but memoizes the smaller subproblem solutions.

The provided sample$/$driver code will

import time

def num$\_$paths $(m,n)$ :

# TODO: Task $1$ of the assignment

def num$\_$paths$\_$memo$($m$,$ n$)$:

# TODO: Task $2$ of the assignment

#driver code $-$ you do not need to make any changes after this line.

#However, submit a screenshot of the output to report the execution time$/$elapsed time.

start$\_$time $=$ time.time$()$

print $($num$\_$paths $(15,14))$

end$\_$time $=$ time.time$()$

start$\_$time$\_$memo $=$ time.time$()$

print$($num$\_$paths$\_$memo $(15,14$do the runtime calculation for you. Take a screenshot of the output and submit it along with your python script.

Expectef Output

$$ The expected result for m$=15,$ n$=14$ is $20058300.$

$$ The elapsed time$/$runtime can vary from system to system.