LeetCode - 动态规划 - 爬楼梯（青蛙跳台阶）

分手后的思念是犯贱 2023-02-17 08:56 36阅读 0赞

*  题目：爬楼梯（青蛙跳台阶）
 *  难度：简单
 *  题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。**每次你可以爬 1 或 2 个台阶**。你有**多少种不同的方法**可以爬到楼顶呢？
 *  示例1：输入： 2 输出： 2  
    解释： 有两种方法可以爬到楼顶。  
    方法一 ：1 阶 + 1 阶  
    方法二： 2 阶
 *  示例2：输入： 3 输出： 3  
    解释： 有三种方法可以爬到楼顶。  
    方法一 ：1 阶 + 1 阶 + 1 阶  
    方法二 ：1 阶 + 2 阶  
    方法三 ：2 阶 + 1 阶

**解题思路**：  
假设当n=1时，只有一种方法到达1楼，那就是从0楼上一层，进而到达1楼，即到达一楼一共有1种方法，即**m(1)=1**

假设当n=2时，你可以从0楼上两层，或者，从1楼上上一层，进而到达2楼，那么，你到达二楼的总方法就是：到达一楼的方法 + 1 = 2，即到达二楼共有2种方法,即**m(2)=m(1) + 1 = 2**

假设当n=3时，你可以从1楼上两层，或者，从2楼上一层，进而到达3楼，那么，你到达三楼的总方法就是：到达二楼的总方法+到达一楼的总方法 = 2 + 1 = 3，即到达三楼一共有3种方法，即**m(3)=m(2) + m(1) = 2**

假设当n=4时，你可以从2楼上两层，或者，从3楼上一层，进而到达4楼，那么，你到达四楼的总方法就是：到达2楼的总方法+到达3楼的总方法 = 2 + 3 = 5，即到达四楼一共有5种方法。即**m(4)=m(3) + m(2) =5**

以此类推… …

假设当n=n时，你可以从n-2楼上两层，或者，从n-1楼上一层，进而到达n楼，那么，你到达n楼的总方法就是：到达n-2楼的总方法+到达n-1楼的总方法=**m(n-2) + m(n-1) = m(n)**

**解题图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]  
**数学函数表达式**  
![在这里插入图片描述][20200613121151969.png]

C语言迭代算法：  
![在这里插入图片描述][20200613115142939.png]

int climbStairs(int n){ 
        int f1 = 1;
        int f2 = 2;
        int f;
    
        if(n == 1){ 				//当楼梯是一层时
            f = f1;
        }else if(n == 2){ 		//当楼梯是两层时
            f = f2;
        }else if(n <= 0){ 		//当楼梯层数小于0，即输入不合法时
            f = 0;
        }else{ 					//当楼梯层数大于2时
            int i;
            for(i=3;i<=n;i++){ 	//迭代计算到达n层时的总方法数
                f = f1 + f2;
                f1 = f2;
                f2 = f;
            }
        }
        
        return f;		//返回到达n楼的总方法数
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020061311564710.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg==,size_16,color_FFFFFF,t_70
[20200613121151969.png]: https://img-blog.csdnimg.cn/20200613121151969.png
[20200613115142939.png]: https://img-blog.csdnimg.cn/20200613115142939.png