Project Objectives:

Part $1.$ Implement a Naive recursive algorithm to solve the problem. Name the file "Staircase$\_$naive.py$"$

Part $2.$ Implement a dynamic programming approach using bottom$-$up technique. Name the file "Staircase$\_$bottom$\_$up$.$py$"$

Part $3.$ Implement a dynamic programming approach using top$-$down technique $($memoization$).$ Name the file "Staircase$\_$top$\_$down.py$"$

Provide a report discussing the differences in the runtime of the codes you have written and how$/$why different they are.$("$Report$\_$FirstName$\_$lastname.docx"$)$

Instructions:

Use IDE of your choice to write the code.

Make sure your python file for each part can be executed outside IDE environment $($no dependency on any other file$)$

Ensure the Python file is named exactly as defined for each part.

just one number as input is can be read from the user by the following prompt $("$Please provided the number of stairs:"$),$ the answer should appear in a new line as $("$The number of distinct ways to reach the top of the staircase is: $")$

Do not write the answer to file, not needed

Do not use built$-$in function for sorting or finding max, etc., follow the guideline discussed in the class and related slides.

You need to measure the time it took to run each of the codes $($with in the code, not using bash, script, etc., use python "time.time$()"),$ the results of this part should appear after when you printed the distinct ways to reach the top, in a new line "Time to execute is:$"$