leetcode70（难度：简单）爬楼梯

短命女 2023-01-13 06:29 67阅读 0赞

## 题目： ##

> 假设你正在爬楼梯。需要 n阶你才能到达楼顶。
> 
> 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
> 
> 注意：给定 n 是一个正整数。
> 
> 示例 1：
> 
> 输入： 2  
> 输出： 2  
> 解释： 有两种方法可以爬到楼顶。
> 
> 1.  1 阶 + 1 阶
> 2.  2 阶  
>     示例 2：
> 
> 输入： 3  
> 输出： 3  
> 解释： 有三种方法可以爬到楼顶。
> 
> 1.  1 阶 + 1 阶 + 1 阶
> 2.  1 阶 + 2 阶
> 3.  2 阶 + 1 阶

这个是典型的动态规划问题

当n小于2的时候，结果就是n。

当n大于2的时候，当n=3的时候，等于n=2和n=1的结果之和。就可以得出：*f*(*x*)=*f*(*x*−1)+*f*(*x*−2)这个公式。

## 代码： ##

#### 方法一：递归法 ####

*f*(*x*)=*f*(*x*−1)+*f*(*x*−2)

package cn.lbl.face.leetCode;
    
    public class 爬楼梯_递归 { 
        public static void main(String[] args) { 
            int result = climbStairs(4);
            System.out.println(result);
        }
    
        public static int climbStairs(int n) { 
            //小于等于2的时候，直接返回n
            if (n <= 2) { 
                return n;
            }
            int result = climbStairs(n - 1) + climbStairs(n - 2);
    
            return result;
        }
    }

但这个在leetcode上提交的时候，会出现在n=45时，参数超时。

所以，我这边又想到了把递归转换为for循环。

#### 方法二：递归转循环 ####

public class 爬楼梯_for循环 { 
        public static void main(String[] args) { 
            int result = climbStairs(4);
            System.out.println(result);
        }
    
        public static int climbStairs(int n) { 
            //小于等于2的时候，直接返回n
            if (n <= 2) { 
                return n;
            }
            int a = 1;
            int b = 2;
            int temp=0;
            for (int i = 3; i < n+1; i++) { 
                temp=b;
                b=a+b;
                a=temp;
            }
            return b;
        }
    }

结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3OTI0OTA1_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3OTI0OTA1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/1f68d2083b61493384f25414b26697cd.png