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, parks$($in$,n)$ that recursively counputes the number of $p$ aths from the top$-$left to bottom$-$right square of an $mxn$ grid without memoization.

$Csc1302/$ DSa $1302$ Homework $2$

Due date: Tue, $13$eb$-202411-59$pM

Write a finction num, pathis$\_$memo$($in$,$ ny$)$ that does the same, but memones the smaller sulproblem solutions.

Use the Pytbon time library to measure the elapsed time of running the functions from steps $1$ aed $2$ with $m=15,n=24.$ The provided sample code will do this calculatice for you if you fill in the functions at the nop. Your mensoized solution should be noticeably faster.

Find a pair of values $(m,n)$ for which the macuozed solution is actually slower than the unmersoized one. Why do you think mensoization is slower here? Leave this information in a comment in your code.