70.爬楼梯
70.1 题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1阶 +1阶2阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1阶 +1阶 +1阶1阶 +2阶2阶 +1阶
提示：
1 <= n <= 45
70.2 题解
找规律
// 方法一：找规律
// 爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。
static int ClimbStairs1(int n)
{
// base case: 如果楼梯数量为 1 或 2，直接返回对应的方法数
if (n <= 2)
{
return n;
}
// 初始化前两个台阶的方法数
int first = 1; // 到达第一个台阶的方法数
int second = 2; // 到达第二个台阶的方法数
// 从第三个台阶开始计算到达每个台阶的方法数
for (int i = 3; i <= n; i++)
{
// 计算当前台阶的方法数，即前两个台阶的方法数之和
int current = first + second;
// 更新前两个台阶的方法数，为下一次循环做准备
first = second;
second = current;
}
// 返回到达第n个台阶的方法数
return second;
}
70.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
// 示例 1：
// 输入：n = 2
// 输出：2
// 解释：有两种方法可以爬到楼顶。
// 1. 1 阶 + 1 阶
// 2. 2 阶
// 示例 2：
// 输入：n = 3
// 输出：3
// 解释：有三种方法可以爬到楼顶。
// 1. 1 阶 + 1 阶 + 1 阶
// 2. 1 阶 + 2 阶
// 3. 2 阶 + 1 阶
#endregion
#region 测试
// 示例 1
int n1 = 2;
int result1 = ClimbStairs1(n1);
Console.WriteLine($"示例1 输出：{result1}");
// 示例 2
int n2 = 3;
int result2 = ClimbStairs1(n2);
Console.WriteLine($"示例2 输出：{result2}");
#endregion
}
#region 答案
// 方法一：找规律
// 爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。
static int ClimbStairs1(int n)
{
// base case: 如果楼梯数量为 1 或 2，直接返回对应的方法数
if (n <= 2)
{
return n;
}
// 初始化前两个台阶的方法数
int first = 1; // 到达第一个台阶的方法数
int second = 2; // 到达第二个台阶的方法数
// 从第三个台阶开始计算到达每个台阶的方法数
for (int i = 3; i <= n; i++)
{
// 计算当前台阶的方法数，即前两个台阶的方法数之和
int current = first + second;
// 更新前两个台阶的方法数，为下一次循环做准备
first = second;
second = current;
}
// 返回到达第n个台阶的方法数
return second;
}
#endregion
}
70.4 运行结果
示例1 输出：2
示例2 输出：3
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
