首页 > 学院 > 开发设计 > 正文

LeetCode 70. Climbing Stairs

2019-11-14 09:08:31
字体:
来源:转载
供稿:网友

描述

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.

分析

设 f (n) 表示爬 n 阶楼梯的不同方法数,为了爬到第 n 阶楼梯,有两个选择: • 从第n−1阶前进1步; • 从第n−1阶前进2步; 这是一个斐波那契数列。 方法 1:递归,太慢; 方法 2:迭代,也可以看作动态规划。 方法3:数学公式。斐波那契数列的通项公式为 an=15‾‾√⎡⎣⎢⎢(1+5‾‾√2)n−(1−5‾‾√2)n⎤⎦⎥⎥

代码

// 迭代,时间复杂度 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; prev = tmp; } return cur; }};// 数学公式,时间复杂度O(1),空间复杂度O(1)class Solution {public: int climbStairs(int n) { const double s = sqrt(5); return floor((pow((1+s)/2, n+1) - pow((1-s)/2, n+1)) / s ); }};
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表