爬楼梯

问题描述

假设你正在爬楼梯。需要 n 步你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 步 + 1 步 2. 2 步

解决方案

f(n)=f(n−1)+f(n−2) f ( n ) = f ( n − 1 ) + f ( n − 2 ) ，斐波那契数列。

1

递归，超出时间限制（21 / 45 个通过测试用例）。

class Solution { int sum=0; public int climbStairs(int n) { if(n==1) { return 1; }else if(n==2) { return 2; } return sum+climbStairs(n-1)+climbStairs(n-2); } }

2

迭代：

class Solution { public int climbStairs(int n) { int sum=0; if(n<3&&n>=0) { sum= n; } int f1=1,f2=2; for(int i=3;i<=n;i++) { sum=f1+f2; f1=f2; f2=sum; } return sum; } }

3

使用斐波那契数列通项公式。推导过程参考链接。 a(n)=15√[(1+5√2)n−(1−5√2)n] a ( n ) = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] ，

class Solution { public int climbStairs(int n) { double p=Math.sqrt(5); double sum=1/p*( Math.pow((1+p)/2, n+1)-Math.pow((1-p)/2, n+1) ); return (int) sum; } }