70.爬楼梯 - 图1

1.题目

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

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

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

示例 1：

  1. 输入： 2
  2. 输出： 2
  3. 解释： 有两种方法可以爬到楼顶。
  4. 1.  1 阶 + 1 阶
  5. 2.  2 阶
  7. 输入： 3
  8. 输出： 3
  9. 解释： 有三种方法可以爬到楼顶。
  10. 1.  1 阶 + 1 阶 + 1 阶
  11. 2.  1 阶 + 2 阶
  12. 3.  2 阶 + 1 阶

2.思路

我们大概写几个来试一下：

当n=0时，代表你已经在楼顶了，不需要走了，这种情况排除。

当n=1时，只有走一步，只有一种方法。

当n=2时，你可以走两个一步，也可以走一个两步，所以有两种方法。

当n=3时，你可以走三个一步，也可以先走一个两步再走一个一步，也可以先走一个一步再走两个两步。

当n=4时，你可以走四个一步，也可以先走两个一步再走一个两步，或者先走一个两步再走两个一步，或者先走一个一步再走一个两步再走一个一步，或者走两个两步。

……

得到规律，当n≥2时，满足函数f(x) = f(x-1) + f(x-2)

显然这是一个斐波那契数列，也就满足一个特性：这个数列从第3项开始，每一项都等于前两项之和。

我们定义三个变量：p、q、r 其中p、q的初始值为0，r的初始值为1

我们用r的目的是为了存放p+q的和，也为了作为一个中间量进行传递

由此我们可以给出代码

    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }