精选50题之 70. 爬楼梯

Bertha 。 2024-04-18 23:31 60阅读 0赞

### 腾讯精选练习（50 题）之 70. 爬楼梯 ###

*   *  原题目链接
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式
     *  数学方法
     *  写在最后

## [原题目链接][Link 1] ##

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

## 题目分析 ##

乍一看和 [上一题][Link 2] 有些相近，“两种移动方式要求移动到终点，没有选后顺序限制”。但其实有一个很大的区别在于，除了上一题是在二维空间而本题是在一维空间内，**本题的两种移动方式的对应次数是未知的**，而上一题是给出的：m-1 和 n-1。

直观的感觉就是，使用数学方法（组合数）并不简单，因为要先讨论所有的移动次数情况，然后分别求组合数并相加。复杂程度很高。  
相反，诸如动态规划这样的“计算机算法”就会很简单了——对一维空间内求解。

## 解题分析 ##

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，这意味着，可以使用动态规划来解决这一问题。  
第 i 阶可以由以下两种方法得到：

1.  第（i - 1）阶向上爬一阶
2.  第（i - 2）阶向上爬两阶

则dp\[ i \] = dp\[i - 1\] + dp\[i - 2\]  
同时，需要初始化dp\[1\] = 1 和 dp\[2\] = 2。

## 代码实现 ##

class Solution {
        
    public:
        int climbStairs(int n) {
        
             if (n == 1) {
        
                return 1;
            }
            int dp[n + 1] = {
        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];
        }
    };

![在这里插入图片描述][20190915134137566.png]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(N)

## 其他方式 ##

动态规划可解的题目，（记忆）递归方法一般也解。

class Solution {
        
    public:
        int climbStairs(int n) {
        
            int memo[n+1] = {
        0};
            return climb_Stairs(0, n, memo);
        }
        int climb_Stairs(int i, int n, int memo[]) {
        
            if (i > n) 
            {
        
                return 0;
            }
            if (i == n) 
            {
        
                return 1;
            }
            if (memo[i] > 0) 
            {
        
                return memo[i];
            }
            memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
            return memo[i];
        }
    };

那么数学方法可解么？可以。

## 数学方法 ##

**一、斐波那契数**：对于动态规划的改进，对空间复杂度的优化到O(1)  
由斐波那契数的定义可知，dp\[i\] 其实就是第 i 个 斐波那契数，因此：

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;
        }
    };

复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(1)

前方高能  
**二、斐波那契公式**  
既然是要找第n个斐波那契数，那…可以直接代入公式啊?  
[参考][Link 3]  
![在这里插入图片描述][2019091513591018.png]

class Solution {
        
    public:
        int climbStairs(int n) {
        
            double sqrt5 = sqrt(5);
            double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
            return (int)(fibn / sqrt5);
        }
    };

复杂度分析：

*  时间复杂度：O(log(N)) ，pow利用的时间
 *  空间复杂度：O(1)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
    **三、Binets 方法**  
    [参考][Link 3]

## 写在最后 ##

数学还是数学

[Link 1]: https://leetcode-cn.com/problems/climbing-stairs/
[Link 2]: https://blog.csdn.net/weixin_41728431
[20190915134137566.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5fd128f9a5d940fa9b40120328dc0cac.png
[Link 3]: https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/
[2019091513591018.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/123a01b3cf3240b593a1208631832533.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/955afba082584e7384c38227c1b1c826.png