Question $4$: Counting Change

Recall the CountChange procedure that we saw in class. In this problem, we are given coins of

$n$ denominations, $d_1,d_2,$dots,$d_n($in cents$),$ and the goal is to find the number of ways of making

change for $N$ cents.

We denoted by CountChange $(r,j)$ the number of ways of making change for $r$ cents using coins

of denominations $d_j,d_{j+1},$dots,$d_n.$ For this function, we wrote a recursive formulation:

We observed that the total number of distinct recursive calls $($when starting with $r=N$ and

$j=1)$ is $O(Nn),$ which led to a memory requirement of $O(Nn)$ and a time complexity of

$O(N^{2}n).$ Suppose now that we want to improve the running time of this procedure. One

simple idea is to observe that if we were given a $j,$ and we wanted to compute the values of

CountChange $(0,j),$ CountChange $(1,j),$dots, CountChange $(N,j),$ we could do this given the

values CountChange $(0,j+1),$ CountChange $(1,j+1),$dots, CountChange $(N,j+1).$

Using this observation, show how one can compute CountChange $(N,1)$ using a space complexity

only $O(N).$