LeetCode小白菜笔记[18]：Climbing Stairs

70. Climbing Stairs [easy]

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，考虑顺序，将其拆分成1和2的连加形式，那么有多少种不同的拆分方法？

比如 2 = 2, 2 = 1+1，两种，3 = 1+1+1, 3 = 1+2， 3 = 2 + 1 ，三种。相当于爬楼梯，每次只能上1或2个台阶，要爬到n楼有几种不同的方法？

考虑到，对于k个台阶的楼梯，假设爬到最顶上，那么倒数第一步只有两种可能，要么是从第k-1阶爬一个台阶上来，要么是从第k-2个台阶爬两个台阶上来。自然地，到达k阶的所有可能的方法的集合也被分成两组，一组是从k-1，一组是k-2来的。到第k阶的方法的总数就是到达第k-1阶的方法总数加上到达第k-2阶的方法总数。于是我们有递推关系式：

f (k) = f (k - 1) + f (k - 2), k \geq 3, k \in Z

可以看出这是一个类似Fibonacci数列的递推关系，前两项求出来以后就可以递推计算后面任何项了。f(1) = 1，显然。f(2) = 2, 1+1 或者直接2。因此可以通过iteration或者recursion来写代码：

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        f1 = 1
        f2 = 2
        r = 0
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            for i in range(n-2):
                r = f1 + f2
                f1 = f2
                f2 = r
            return r

（-_-||。。。LeetCode要维护了。。。提交不上去，正当理由偷懒）

好，接着昨天的继续：

提交结果：30ms，beat 59.05%

可以用递归的方法重写一遍，如下：

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

应该可以解决，但是无奈超时了。

2018年2月11日21:55:54

玩了一天回到家，美滋滋~