题目
70. 爬楼梯 - 力扣（LeetCode）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
代码语言：javascript复制输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶示例 2：
代码语言：javascript复制输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示： 1 <= n <= 45
题解 其实就是 动态规划
将 本问题 分解为 多个 子问题, 爬上 第 n 阶楼梯的方法数量 等于以下 两 部分之和
- 爬上 n-1 阶楼梯的方法数量, 因为再爬1阶就能到第 n 阶
- 爬上 n-2 阶楼梯的方法数量, 因为再爬2阶就能到第 n 阶 于是可得 dpn = dpn−1 dpn−2 初始化
dp0 = 1
dp1 = 1
时间复杂度:
O(n)
代码语言：javascript复制public class Solution {
#region 方法2: 循环
public int ClimbStairs(int n)
{
if (n <= 1)
{
return 1;
}
// 注意: 长度: n 1
int[] arr = new int[n 1];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < arr.Length; i )
{
// arr[2] = arr[1] arr[0]
// arr[3] = arr[2] arr[1]
// arr[4] = arr[3] arr[2]
// ...
// 在循环内最后一次: 再i , 就会达到 Length, 从而不满足循环条件而退出
// arr[n] = arr[n - 1] arr[n -2]
arr[i] = arr[i - 1] arr[i - 2];
}
return arr[n];
}
#endregion
}
public class Solution {
#region 方法3: 循环 压缩优化
/// <summary>
/// dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，没有必要存储所有计算过的 dp 项。用两个临时变量去存这两个状态就好
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public int ClimbStairs(int n)
{
int prev = 1, cur = 1;
int temp;
for (int i = 2; i < n 1; i )
{
temp = cur; // 暂存上一次的 cur
cur = prev cur; // 当前的 cur = 上上次cur 上一次cur
prev = temp; // prev 更新为 上一次 cur
}
return cur;
}
#endregion
}
Q&A 补充 参考 感谢帮助！
画解算法：70. 爬楼梯 - 爬楼梯 - 力扣（LeetCode）
本文作者： yiyun
- 本文链接： https://cloud.tencent.com/developer/article/2237169
- 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
