LeetCode初级算法之动态规划：70 爬楼梯

题目信息

题目地址： leetcode-cn.com/problems/cl…

假设你正在爬楼梯。需要 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 阶
复制代码

思路一：斐波那契数列

我们可以看先推演几个看看

1. 一个台阶：
   只有一种跳法就是跳一格
2. 两个台阶：
   跳一格跳两次和跳一次2格的
3. 三个台阶：
   1+1+1、2+1、1+2（共三种）
4. 四个台阶：
   1+1+1+1、2+1+1、1+2+1、1+1+2、2+2（共五种）
5. 五个台阶
   1+1+1+1、2+1+1+1、1+2+1+1、1+1+2+1、1+1+1+2、2+2+1、2+1+2、1+2+2（共八种）

我们可以得到一个规律，他是一个斐波那契数列，题目正整数就不从数列的第0个搞起了直接从第一个开始

斐波那契数列它是有公式的通过n直接计算出result。