What’s the space complexity for the staircases problem?
Hi Alex!
If we solve it using a brute force recursive method, the space complexity is O(n) to store the recursion stack. The space complexity for both the dynamic programming solutions is also O(n). The memory optimization solution reduces the complexity to O(1).
These are all explained within the lesson as well.