LeetCode #70 Climbing Stairs

The Objective: You are climbing a staircase with N number of steps, each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

This is a classic problem, a perfect example of why I love leetcode so much. I am pretty familar with this one so code above is the standard solution. But as per usual after the problem I went around digging for some youtube videos that discuss this problem or hit on Recursive Programming.

Recursive programming

Recursion in Computer Science is the concept that a problem can be solved from smaller solutions. Kind of like using tree branches to slowly get to the trunk. The above image shows the tree like shape of the code. The only issue is there's a slight ineffciency when it comes to effciency. As can be seen highlighted in red to find new_ways(4) you need to calculate nw(2) twice. The solution is to do as I did in my own code using the bottem up approach. This means instead of needing all the elements in the tree you just need the last two to determine the next value.

Lessons Learned:

This was a great refresher on A core concepts in programming. Dynamic Progamming. As much as a hate to admit it I often brute force my way to a solution first, but this was a case where I was familiar with the concept of the problem and just did a quick refresher on recursive/dynamic python script to figure it out.