Dynamic Programming$]$

In this exercise, we will count the number of ways to make change for c cents $($for an illustration,

watch the SpongeBob SquarePants episode $$Squid$$s Day Off$$ from $4$:$25$ to $4$:$45)$

In the problem, coins are available in k denominations $$0\mathrm{.}01=$ d$0<$ d$1<<$ dk$1,$ with at

least c coins of each denomination available.

The problem comes down to a choice: given an amount $$ and a coin j with value dj$,$ count

the number of ways to make $$ cents with coin j and count the ways to make $$ cents without

coin j and add the ways. Of course, if dj $>,$ then the coin cannot be included.

a$.$ There are two base cases for the recursive function. Explain the purpose of each.

b$.$ Given the base cases and the include$-$don$$t include approach, derive a recursive func$-$

tion to compute the number of ways to make c cents.

c$.$ Given coins in denominations $$0\mathrm{.}01,$ $$0\mathrm{.}02,$ $$0\mathrm{.}03$ and $$0\mathrm{.}05,$ show the completed ta$-$

ble used in a dynamic program to count the number of ways to make $$0\mathrm{.}11.$

$3$ of $7$