Q70 Climbing Stairs

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.

Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解题思路：

此题通过观察 n=2, 3, 4, ... 等步数的规律，发现是一个菲波那切数列，即 f(n) = f(n-1) + f(n-2)，递归求解即可。

这里没有使用递归，采用动态规划的思想，只保留前两个状态。

Python实现：

# 动态规划
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        one = 0; two = 0;  # 保留前两个状态
        step = 1
        while n > 0:
            one = two
            two = step
            step = one + two
            n -= 1
        return step

a = 3
b = Solution()
print(b.climbStairs(5)) # 8 # f(5) = f(4) + f(3)