算法45：动态规划专练(力扣70: 爬楼梯 力扣746：使用最小花费爬楼梯)

力���70题：爬楼梯

（）

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

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

（）

示例 1：

输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶

示例 2：

输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶

分析：

1. 如果有1个楼梯，那只能走1步登顶。 1中方法

2. 如果有2个楼梯。

           a. 我们可以一次走一步登顶。  

            b. 也可以一次走2步，登顶。 

累计就是2种方法。

3. 如果有3个楼梯：

     a. 从楼底一步一步走上来

     b. 从楼底先走1步，再一次走2步上来

     c. 从楼底先一次走2步，再走1步上来

    累计就是3种方法。

    状态转移分析：

    分析1： 步骤a是一步一步走上来的，也就是说要想走到3阶楼梯，前一次是从2阶楼梯上来的.

    分析2： 步骤c是先从楼底一次走2步，然后一次走一步。也还是从2阶楼梯走上来的

    也就是说 步骤a和步骤c，都依赖2阶楼梯的走法。而我们上面分析过了，从楼底走到2阶楼梯有      2 种方法.

     分析3： 步骤b先从楼底走一步，最后一次走2步登顶。也就是说想要走到3阶楼梯，也可以从1      阶楼梯直接一次走2步直接登顶。依赖1阶楼梯

    按照这种思路:  从楼底走到1阶楼梯有1种方法，从楼底走到2阶楼梯有2中方法。而3阶楼梯依赖     1阶楼梯和2阶楼梯。本体是要求一共多少种走法，那就是1阶楼梯和2阶楼梯的累加和。

    得到公式： F(n) = F(n-1) + F(n-2).  n > 2.

   递归代码：

   public int climbStairs(int n)    {        if (n  2. 那我假设 n== 4，那么推导过程： 
 第一步：
 

开始位置	1阶段楼梯	2阶段楼梯	3阶段楼梯	4阶段楼梯
楼底	根据 n