748
[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
* 來源：https://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
* 來源：https://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
* 來源：https://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;
}
最後更新：2017-04-03 12:54:47