LeetCode70. Climbing Stairs题解

1. 题目描述

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? 【翻译过来】：给了一个数n代表了n层台阶，每次可以选择上1或者2层台阶，那么求最终上够n层台阶可以有多少种走法。

2. 分析

刚开始拿到这个题目的时候，我的思想就是非常简单的排列组合的想法：当还剩的步骤大于等于2的时候每一次都有2种选择。 事实证明这种思路难以实现，不过换一个思路就可以柳暗花明又一村了：

台阶数n=0的时候，很显然走法为0；台阶数n=1的时候，很显然只有1种走法——直接走1步；台阶数n=2的时候，很显然有2种走法——走2个1步或者直接2步；台阶数n>2的时候，当前阶数的走法n等于前一阶数(n-1)的走法加上再前一阶数(n-2)的走法，犹如斐波那契数列一样。 这是因为当前阶数n：要么是由前一阶n-1上1层台阶得到，要么是由再前一阶n-2上2层台阶得到。所以n的走法就有n-2时候的走法与n-1时候的走法之和得到。

3. 源码

class Solution { public: int climbStairs(int n) { if (n <= 2) { return n; } int stepN2 = 1, stepN1 = 2; int current; for (int i = 3; i <= n; i++) { //当前阶数n的走法 = n-1走法 + n-2走法 current = stepN2 + stepN1; //更新n-2 stepN2 = stepN1; //更新n-1 stepN1 = current; } return current; } };

4. 心得

能够理解本题的隐藏的斐波那契数列的特性之后，问题就变得简单易解了。