$$ Details

Sweepy is a robot that cleans a carpet modeled as an $mn$ grid, carpet. If carpet $[i,j]=1,$ then the carpet at position $(i,j)$ is dirty. Otherwise, we have carpet $[i,j]=0.$ Sweepy starts at cell $(0,0)$ and can travel right or down.

Give a dynamic programming algorithm that maximizes the number of dirty cells visited by Sweepy.

Define the subproblems for your solution.

Give a recursive formulation to solve the subproblems. Include the base cases.

Give pseudocode for a memoized, top$-$down algorithm that outputs this maximum.

Give pseudocode for an efficient, bottom$-$up algorithm that outputs this maximum.

What is the runtime of your solution? Justify your answer.

Explain how to modify your algorithm to output the path taken by Sweepy.