码疯窝

LeetCode 每日一题 — Climbing Stairs

2015/02/05 11:29:44    分类: 日志连载    0人评论 次浏览

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?

算法分析: 此题就是个纯数学题目了, 理解好题目意思, 就能得出以下结果, 上n阶楼梯的方法S(n), 可以分成: 上n-1阶楼梯方法再走一步1, 上n-2 阶楼梯方法再走2步.
因此我们可以得出 S(n) = S(n – 1) + S(n – 2), 一看这个公式是不是很眼熟? 没错, 这正好是斐波那契数列.
斐波那契数列的通项公式是: a(n) = ((1+√5)/2)^n /√5 - ((1-√5)/2)^n /√5, 当然用通项公式有点偷懒的嫌疑, 不过至少证明了这里的确是斐波那契数列.
因此 Java 和C++ 用了普通的O(n)算法, Python 用的是通项公式.

Java:

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] s = new int[n];
        s[0] = 1;
        s[1] = 2;
        for(int i = 2; i < n; i++) {
            s[i] = s[i - 1] + s[i - 2];
        }
        return s[n - 1];
    }
}

C++:

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n;
        
        int* s = new int[n];
        s[0] = 1;
        s[1] = 2;
          
        for(int i = 2; i < n; i++) {
            s[i] = s[i - 1] + s[i - 2];
        }
        return s[n - 1];
    }
};

Python:

class Solution:
    def climbStairs(self, n):
        return int((((1 + 5**0.5) / 2) ** (n + 1) - ((1 - 5**0.5) / 2) ** (n + 1)) / 5**0.5)
继续查看有关 日志连载的文章

0个访客评论