70. Climbing Stairs

Problem:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Classical Dynamic Programming Problem.

  • 0 step, 0 way
  • 1 step, 1 way
  • 2 step, 2 ways (1,1 & 2)
  • n step, (n-1) step's ways + (n-2) step's ways

So, the i's step ways denote as d(i).

d(i) = d(i-1) + d(i-2).

It's a fibonacci sequence. So, one way to direct calc:

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        import math
        sqrt5 = math.sqrt(5)
        return int(sqrt5 / 5 * (((1+sqrt5)/2)**(n+1) - ((1-sqrt5)/2)**(n+1)))

And iteration way:

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        x, y = 0, 1
        while n:
            y, x, n = x + y, y, n-1
        return y

Continue...