题目英文
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
题目中文
假设你正在爬楼梯。需要 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 阶
示例 3：
输入： 44
输出： 1134903170
算法实现
分析这个题目：
- 1 阶，f(1) = 1 种方案
- 2 阶，f(2) = 2 种方案
- 3 阶，f(3) = 3 种方案
- 4 阶，f(4) = 5 种方案
- ……
- n 阶，f(n) = f(n-1) + f(n-2) 种方案
即，该问题可以转换为斐波那契数列问题。
方案一：利用递归
public class Solution {
public int ClimbStairs(int n) {
if (n <= 2)
return n;
return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}
}
由于递归的执行速度，远远小于循环，导致“超出时间限制”。
方案二：利用循环
public class Solution {
public int ClimbStairs(int n) {
if (n <= 2)
return n;
int first = 1;
int second = 2;
int result = 0;
for (int i = 3; i <= n; i++)
{
result = first + second;
first = second;
second = result;
}
return result;
}
}
实验结果
- 状态：通过
- 45 / 45 个通过测试用例
- 执行用时: 52 ms, 在所有 C# 提交中击败了 97.87% 的用户
- 内存消耗: 13.7 MB, 在所有 C# 提交中击败了 5.98% 的用户
相关图文：
- LeetCode实战：两数之和
- LeetCode实战：三数之和
- LeetCode实战：缺失的第一个正数
- LeetCode实战：求众数
- LeetCode实战：快乐数
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
- LeetCode实战：搜索二维矩阵
转载：https://blog.csdn.net/LSGO_MYP/article/details/99928535
查看评论