版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

• Climbing Stairs
  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步能走到顶。每步能走一阶或两阶。有多少种不同的方式到达顶端。
• 思路：最常见的是递归解法，也很好理解
  代码：

int climbStairs(int n)
{
    if(n<=0) return 0; // 当台阶数小于等于0时
    if(n==1) return 1; // 当台阶数等于1时，只有一种走法，即走一步就能到顶
    if(n==2) return 2; // 当台阶数等于2时，有两种走法，即走一步或走两步到顶
    return climbStairs(n-1) + climbStairs(n-2); // 台阶数大于2，继续递归，下一步可能走一步，也可能走两步
}

这种思路能AC大多数的OJ平台，但是在牛客网却AC不了，那么他还有另外一种思路，即可以把走台阶问题看成是斐波那契数列问题，理由如下：

• 该问题本质为斐波拉契数列

1. 假设当有n个台阶时假设有f(n)种走法；
2. 最后一步要么跨1个台阶要么跨2个台阶；
3. 当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法；
4. 当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2 )种走法；
5. 显然n个台阶的走法等于前两种情况的走法之和即f(n) = f(n-1) + f(n-2)。

• f(n) = f(n-1) + f(n-2) 即为斐波那契数列的递推关系式，则的证这是一个斐波那契问题。
• 代码：

int climbStairs_1(int n)
{
    if (n < 3)
        return n;
    int one_step_before = 2;
    int two_steps_before = 1;
    int all_ways = 0;
    for (int i = 2; i < n; i++)
    {
        all_ways = one_step_before + two_steps_before;
        two_steps_before = one_step_before;
        one_step_before = all_ways;
    }
    return all_ways;
}

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~