On page 254 we noted that calculating a single value p k (n) by the recursive definition may…
On page 254 we noted that calculating a single value pk(n) by the recursive definition may require many steps, since each term splits into two terms that must also be calculated recursively, and may call for redundant calculations. 22
(a) If we want to find not just one pk(n) but all pk(n) up to some maximum values of k and n, there is a more efficient way, which requires just a single addition to calculate each one. This is achieved by starting with the base cases and then working up from smaller cases to larger ones, tabulating the results along the way, such that the values pk−1(n − 1) and pk(n − k) are already present in the table when we need to calculate pk(n).
Complete the following table with the values of pk(n) for 1 ≤ k, n ≤ 10, proceeding from top to bottom and within each row from left to right. The base cases are already filled in.
(b) To find just a single value pk(n), it is still useful to record intermediate results in a table, though it is not necessary to fill in every cell. Find p5(10) as follows: Start by circling its corresponding cell. Then circle the two cells whose values are used to compute p5(10). For each newly circled cell, circle the two cells that it depends on, and repeat until reaching the base cases. Finally, proceed from top to bottom and left to right, filling in only the circled cells, until reaching p5(10).