[LeetCode]70.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?

【题意】

爬楼梯。爬到楼顶需要n步。

每一次你都可以爬一步或者爬两步，问有多少种方式爬到楼顶？

【分析】

设 f (n) 表示爬 n 阶楼梯的不同方法数，为了爬到第 n 阶楼梯，有两个选择：
• 从第 n  - 1 阶前进 1 步；
• 从第 n  - 2 阶前进 2 步；
因此，有 f (n) = f (n  - 1) + f (n  - 2)。

这是一个斐波那契数列。

详细分析请参考：编程之美之斐波那契数列

【代码1】

// 递归
class Solution {
public:
    int climbStairs(int n) {
        return Fibonacci(n);
    }
private:
    int Fibonacci(int n){
        if(n <= 2){
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

【代码2】

/*********************************
*   日期：2014-01-23
*   作者：SJF0115
*   题号: Climbing Stairs
*   来源：http://oj.leetcode.com/problems/climbing-stairs/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
// 迭代，时间复杂度 O(n)，空间复杂度 O(1)
class Solution {
public:
     int climbStairs(int n) {
        int prev = 0;
        int cur = 1;
        for(int i = 1; i <= n ; ++i){
            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
        return cur;
    }
};
int main() {
    Solution solution;
    int result;
    result = solution.climbStairs(40);
    printf("Result:%d\n",result);
    return 0;
}

【代码3】

/*********************************
*   日期：2014-01-23
*   作者：SJF0115
*   题号: Climbing Stairs
*   来源：http://oj.leetcode.com/problems/climbing-stairs/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
// 数学公式，时间复杂度 O(1)，空间复杂度 O(1)
class Solution {
public:
    int climbStairs(int n) {
        double s = sqrt(5);
        return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5);
    }
};
int main() {
    Solution solution;
    int result;
    result = solution.climbStairs(40);
    printf("Result:%d\n",result);
    return 0;
}

【代码4】

/*********************************
*   日期：2014-01-24
*   作者：SJF0115
*   题号: Climbing Stairs
*   来源：http://oj.leetcode.com/problems/climbing-stairs/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;

class Solution {
public:
    //Fibonacci数列
    int climbStairs(int n) {
        if(n == 0){
            return 0;
        }
        int A[2][2] = {1,1,1,0};
        //初始为单位矩阵
        int Matrix[2][2] = {1,0,1,0};
        //n = n - 1;
        for(; n ;n >>= 1){
            //奇偶
            if(n&1){
                MatrixMulti(Matrix,A);
            }//if
            MatrixMulti(A,A);
        }//for
        return Matrix[0][0];
    }
private:
    //矩阵乘法
    void MatrixMulti(int matrix[2][2],int matrix2[2][2]){
        int a = matrix[0][0] * matrix2[0][0] +  matrix[0][1] * matrix2[1][0];
        int b = matrix[0][0] * matrix2[0][1] +  matrix[0][1] * matrix2[1][1];
        int c = matrix[1][0] * matrix2[0][0] +  matrix[1][1] * matrix2[1][0];
        int d = matrix[1][0] * matrix2[0][1] +  matrix[1][1] * matrix2[1][1];
        matrix[0][0] = a;
        matrix[0][1] = b;
        matrix[1][0] = c;
        matrix[1][1] = d;
    }
};

int main() {
    Solution solution;
    int result;
    for(int i = 1;i < 10;i++){
        result = solution.climbStairs(i);
        printf("Result:%d\n",result);
    }
    return 0;
}