$8$ Question: $1.$ Define a dynamicprogramming table and explain the meaning of its entries. $2.$ Write the...

Define a dynamic$-$programming table and explain the meaning of its entries.

Write the initialization step of your algorithm.

Write the recurrence formula for computing entries of the table.

Explain the formula.

Find the running time of your algorithm.

Problem $2.$ A freelance photographer prepares her schedule for the next $n$ days. She may work or rest on each of the days.

If she works on day $i,$ she gets paid $p_i>0$ dollars.

However, she is not paid on those days she rests.

She is not willing to work $3$ days in a row.

Subject to these constraints, the photographer wants to maximize her pay.

Design a polynomial$-$time dynamic programming algorithm that given a sequence of $p_1,$dots,$p_n$ finds an optimal schedule. Describe your algorithm in detail. Prove its correctness. Specifically, do the following: