https://leetcode.com/problems/climbing-stairs

Solution 1:

We can climb either 1 or 2 steps, and we are interested how many ways to climb ladder with n stairs. How can we reach step number n:

  1. Making step with size 1, so from step with number n-1
  2. Making step with size 2, so from step with number n-2.

So, if we denote F[n] numbers of ways to reach step number n, we can write equation: F[n] = F[n-1] + F[n-2]. But it is not enough, we also need to define starting cases: F[1] = 1 and F[2] = 2. Or we can say, that F[0] = 1 and F[1] = 1.

Now, everything is ready to write our dynamic programming problem.

Complexity: time complexity is O(n) and space complexity is O(1).

class Solution:
    def climbStairs(self, n):
        dp = (1, 1)
        for i in range(n-1):
            dp = (dp[1], dp[0] + dp[1])
        return dp[1]

Solution 2

If we look carefully at equation F[n] = F[n-1] + F[n-2] and starting points, we can see, that we have nothing else, than Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Note however, that it is shifted by one position. So, what we need to do is to use Binet formula: https://en.wikipedia.org/wiki/Fibonacci_number#Binet’s_formula, where we use computation by rounding.

Complexity: both time and memory is O(1) if we assume that number in int32 range and if we assume complexity of ** as O(1).

return round((0.5+sqrt(5)/2)**(n+1)/sqrt(5))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0070