Memoization without Recursion
Lesson 5 of 15 in Coddy's Dynamic Programming 101 course.
In the previous lesson, we learned about memoization and how it can help to improve the time complexity of our recursive solutions. In this lesson, we will explore how to use recursion with memoization to solve problems more efficiently.
Recursion is a technique in programming where a function calls itself to solve a problem. Recursive solutions can be very elegant and intuitive, but they can also be inefficient, especially if the same function is called multiple times with the same arguments. This is where memoization comes in. By storing the results of previous function calls, we can avoid redundant calculations and significantly improve the performance of our recursive solutions.
Challenge
EasySuppose you can climb either 1 step or 2 steps at a time.
Write a function called count_ways that takes an integer n and returns the number of ways to climb a staircase of n steps.
The function should be memoized to avoid repeated calculations.
Avoid using recursion in this challenge!
Try it yourself
def count_ways(n):
# TODO: write your code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance