LeetCode题目之腾讯精选练习（50题）：爬楼梯

待我称王封你为后i 2024-04-17 21:36 81阅读 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 阶

## 实现代码 ##

public static int ClimbStairs(int n)
    {
        
        int sum = 0;
        for (int i = 1; i <= n / 2; i++)
        {
        
            decimal fenmu = 1, fenzi = 1;
            int s = n - i;
            for (int j = i; j > 0; j--)
            {
        
                fenmu *= s;
                s--;
            }
            for (int j = i; j > 0; j--)
            {
        
                fenzi *= j;
            }
            sum += (int)(fenmu / fenzi);//运用排列组合的知识
        }
        return sum+1;//补上全是一的情况
    }

## 执行结果 ##

**执行结果**：通过  
**执行用时** : 60 ms, 在所有 C\# 提交中击败了59.06%的用户  
**内存消耗** : 13.8 MB, 在所有 C\# 提交中击败了5.98%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

按照自己的想法用排列组合的知识进行了解答，之后看解析了解了动态规划的方法，由动态规划了解到斐波那锲的方法，以下是斐波那锲方法。

## 官方解答 ##

public static int ClimbStairs2(int n) //fib方法
    {
        
        if (n == 1)
            return 1;
        int first = 1, second = 2;
        for (int i = 3; i <= n; i++)
        {
        
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }

![在这里插入图片描述][20190901172908502.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f0573a844afe4cda8267a9c33eae92bd.png
[20190901172908502.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ce826a9672a542838fa555b413d981a3.png