爬楼梯算法

1、题目描述2、题目分析2.1 图解2.2 方法分析 3、题解心得

1、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶

2、题目分析

2.1 图解

画图分析可以看出，这道题目本质上是斐波那契数列。分析如下图：

2.2 方法分析

根据上图，我们知道，这个可以用递推公式来求解，也可以用递归方法来求。但是以上两个方法都有个共同的弊端-----耗时太多。所以，我采取的方法是利用结果作为中间变量的循环方法。

int climbStairs(int n) { int n1=0,n2=1,result=2; //因为楼层数n<3时，我们已知结果result,故result从第三层开始算起 int i; //所以result等于上一层的结果数，便于循环 if(n<3)return n; for(i=2;i<n;i++) { n1=n2; //n1取代n2 n2=result;//n2取代上一层的结果 result=n1+n2;//相加等于下一层得结果 } return result; }

3、题解心得

这道题对于大多数人来说应该没什么大问题，稍微调试就可以出结果，只是不同的思考方式在计算机上的运行速度也是千差万别的！ 关注 ID: zhd5120153951 ，我们一起打怪升级。