This notebook was prepared by Donne Martin. Source and license info is on GitHub.
To get to step n, we will need to have gone:
If we go the one step route above, we'll be at n-1 before taking the last step. To get to step n-1, we will need to have gone:
Continue this process until we reach the start.
Base case:
Note, if we had chosen n == 0 to return 0 instead, we would need to add additional base cases. Otherwise we'd be adding multiple 0's once we hit the base cases and not get any result > 0.
Recursive case:
We'll memoize the solution to improve performance.
Complexity:
Note: The number of ways will quickly overflow the bounds of an integer.
class Steps(object):
def count_ways(self, num_steps):
if num_steps is None or num_steps < 0:
raise TypeError('num_steps cannot be None or negative')
cache = {}
return self._count_ways(num_steps, cache)
def _count_ways(self, num_steps, cache):
if num_steps < 0:
return 0
if num_steps == 0:
return 1
if num_steps in cache:
return cache[num_steps]
cache[num_steps] = (self._count_ways(num_steps-1, cache) +
self._count_ways(num_steps-2, cache) +
self._count_ways(num_steps-3, cache))
return cache[num_steps]
%%writefile test_steps.py
import unittest
class TestSteps(unittest.TestCase):
def test_steps(self):
steps = Steps()
self.assertRaises(TypeError, steps.count_ways, None)
self.assertRaises(TypeError, steps.count_ways, -1)
self.assertEqual(steps.count_ways(0), 1)
self.assertEqual(steps.count_ways(1), 1)
self.assertEqual(steps.count_ways(2), 2)
self.assertEqual(steps.count_ways(3), 4)
self.assertEqual(steps.count_ways(4), 7)
self.assertEqual(steps.count_ways(10), 274)
print('Success: test_steps')
def main():
test = TestSteps()
test.test_steps()
if __name__ == '__main__':
main()
Overwriting test_steps.py
%run -i test_steps.py
Success: test_steps