爬台阶---算法汇总

悠悠 2023-07-23 11:56 21阅读 0赞

1，leetcode网址

[https://leetcode-cn.com/problems/climbing-stairs/submissions/][https_leetcode-cn.com_problems_climbing-stairs_submissions]

2，题目

假设你正在爬楼梯。需要 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 阶

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/climbing-stairs  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3，解题方法

分析，

第一级：1种，一步跨上去

第二级：2种，1）直接一步跨；2）一级一级走。

第三级：3种，总归是 第一级和第二级的和。

即当前i处台阶，一定是从i-1或者i-2处台阶登上。

即转换成斐波拉契数列问题。

即f(n) = f(n)+f(n-1)

思路一的代码：

class Solution {
    
        //其实转换成斐波拉契数列问题，f(n) = f(n)+f(n-1)
        //使用数组缓存每一步的结果。称之为记忆递归
        public int climbStairs(int n) {
           int[] dp = new int[n+2];
           dp[0] = 0;
           dp[1] = 1;
           dp[2] = 2;
    
           for(int i = 3;i<=n;i++){
               dp[i]  = dp[i-1]+dp[i-2];
           }
    
           return dp[n];
        }
    }

思路二

class Solution {
        
        public int climbStairs(int n) {
           if(n ==1){
               return 1;
           }
    
           int first = 1;
           int second = 2;
    
           for(int i = 3;i<=n;i++){
               int third = first +second;
               first = second;
               second = third;
           }
    
           return second;
        }
    }

[https_leetcode-cn.com_problems_climbing-stairs_submissions]: https://leetcode-cn.com/problems/climbing-stairs/submissions/