Climbing stairs#

Levels: level-3

Algorithms: dynamic-programming

Practice Link#

LeetCode

Description#

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?

Note:

Given n will be a positive integer.

Examples#

1Input: 2
2Output: 2
3Explanation: There are two ways to climb to the top.
41. 1 step + 1 step
52. 2 steps

1Input: 3
2Output: 3
3Explanation: There are three ways to climb to the top.
41. 1 step + 1 step + 1 step
52. 1 step + 2 steps
63. 2 steps + 1 step

Python Solution#

 1class Solution1(object):
 2    def climbStairs(self, n):
 3        """
 4        :type n: int
 5        :rtype: int
 6        """
 7        if not n:
 8            return 0
 9        if n == 1:
10            return 1
11        f = 1
12        s = 2
13        for _ in range(3, n + 1):
14            t = f + s
15            f = s
16            s = t
17        return s
18
19
20class Solution2(object):
21    def climbStairs(self, n):
22        """
23        :type n: int
24        :rtype: int
25        """
26        if not n:
27            return 0
28        if n == 1:
29            return 1
30        dp = [0 for _ in range(n + 1)]
31        dp[1] = 1
32        dp[2] = 2
33        for i in range(3, n + 1):
34            dp[i] = dp[i - 1] + dp[i - 2]
35        return dp[n]
36
37
38tm = [
39    (1, 1),
40    (2, 2),
41    (3, 3),
42    (0, 0),
43    (None, 0),
44]
45
46if __name__ == "__main__":
47
48    sol1 = Solution1()
49    sol2 = Solution2()
50
51    for idx, nin in enumerate(tm):
52        resout = sol1.climbStairs(nin[0])
53        print(nin, resout, resout == nin[1])
54        resout = sol2.climbStairs(nin[0])
55        print(nin, resout, resout == nin[1])