关于爬楼梯问题的详细思路（斐波那契系数）_爬楼梯思路

为了给孩子们讲明白，网上看了很多，但是都是以大家有一定的编程基础来编写的答案，对于基础差或者没基础的朋友来说还是太抽象了，在这里我详细地带朋友们分析一下：

爬楼梯问题（斐波那契算法）思路分析

题目：你正在爬楼梯，楼梯共有x阶。到达顶峰需要y步。每次您都可以爬 1 或 2 级台阶。你能用多少种不同的方式爬到x阶？

思路详解：

1. 首先我们从第一阶开始，上第一阶只需要 1 步，也就是一种方法
2. 第二阶，可以1+1，也可以2，共两种方法。
3. 第三阶，可以1+1+1，1+2，2+1， 共三种方法。那么我们可以拆解为我们是从第一阶或第二阶上去的：
   1. 如果从第一阶上去的， 就有1+1 和 2 两种办法，而上第一阶只有一种方法，所以是1（上第一阶的办法数）* 2 等于两种方法。（1+1+1，1+2）
   2. 如果是从第二阶上去的，只有1 的一种方法，而上第二阶有两种方法，所以就是2（上第二阶的方法数） * 1 等于两种方法。（1+1+1，2+1）
   3. 但是，从第一阶上去的方法里面和从第二阶上去的方法里面都有 1+1+1 的方法，所以我们要将从第一阶上去的方法里面减去这一种方法，因此从第一阶上去的方法里减去重复的1+1+1的方法，那么剩下的总数就是三种方法。
   4. 那么，从第一阶到第三阶的方法为1种，正好等于上第一阶的方法数。
   5. 而从第二阶到第三阶的方法有2种，正好等于上第二阶的方法数。

结论就是上第三阶的方法正好等于上第一阶和上第二阶的方法之和。

1. 同理，我们来看第四阶，每次只能走一阶或两阶，所以只能从第三阶或第二阶上去：
   1. 如果从第二阶上去的，就有就有1+1 和 2 两种办法，而上第二阶有两种方法，所以是2（上第二阶的办法数）* 2 等于四种方法。（1+1+1+1，1+1+2，2+1+1，2+2）
   2. 如果从第三阶上去的，只有1 的一种方法，而上第三阶有三种方法，所以结果就是3（上第三阶的方法数） * 1 等于三种方法。（1+1+1+1， 1+2+1， 2+1+1）
   3. 但是从第二阶上去的和第三阶上去的方法里面都有1+1+1+1和 2+1+1的方法，所以我们要将从第二阶上去的方法里面减去这两种重复的方法，剩下两种方法。剩下总方法数就是五种
   4. 那么，从第二阶到第四阶的方法为两种，正好等于上第二阶的方法数。
   5. 而从第三阶到第四阶的方法有三种，正好等于上第三阶的方法数。

结论就是，上第四阶的方法正好等于上第二阶的方法和上第三阶方法之和。

1. 通过以上的演算，可以得出结论，上第n阶的爬法正好等于上第（n-2）阶与第（n-1）阶的方法之和，Fn(n) = Fn(n-2) + Fn(n-1)。
2. 接下来我们只需要一直重复由高到低的拆解运算直到最下面的第一阶和第二阶即可，因为方法数就是不断地反复计算每一步的方法数累计而成的。

代码：

public static int dpFibonacci(int topStep) {
    if (topStep == 1) return 1;
    else if (topStep == 2) return 2;
    else {
        return dpFibonacci(topStep - 2) + dpFibonacci(topStep - 1);
    }
}