Exercises

The following exercises provide you with the opportunity to practice with dynamic programming. The solutions to these exercises are found in the section .

1. The following function accepts an array of numbers and returns the sum, as long as a particular number doesn’t bring the sum above 100. If adding a particular number will make the sum higher than 100, that number is ignored. However, this function makes unnecessary recursive calls. Fix the code to eliminate the unnecessary recursion:

   ​	​def​ ​add_until_100​(array):
   ​	​if​ ​not​ array:
   ​	​return​ 0
   ​
   ​	​if​ array[0] + add_until_100(array[1:]) > 100:
   ​	​return​ add_until_100(array[1:])
   ​	​else​:
   ​	​return​ array[0] + add_until_100(array[1:])

2. The following function uses recursion to calculate the Nth number from a mathematical sequence known as the Golomb sequence. It’s terribly inefficient, though! Use memoization to optimize it. (You don’t have to understand how the Golomb sequence works to do this exercise.)

   ​	​def​ ​golomb​(n):
   ​	​if​ n == 1:
   ​	​return​ 1
   ​
   ​	​return​ 1 + golomb(n - golomb(golomb(n - 1)))

3. Here is a solution to the unique paths problem from an exercise in the previous chapter. (Sorry, it’s a bit of a spoiler if you haven’t tried doing that exercise yet.) Use memoization to improve its efficiency:

   ​	​def​ ​unique_paths​(rows, columns):
   ​	​if​ rows == 1 ​or​ columns == 1:
   ​	​return​ 1
   ​
   ​	​return​ unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)