爬楼梯
问题描述
假设你正在爬楼梯。需要 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 阶思路
首先想到是递归的方法来计算，递归逻辑climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)，但结果超时，只能用正向的方式，下次迭代的第n-2个台阶的走法等于上次迭代n-1个台阶的走法，下次迭代的第n-1个台阶的走法等于上次迭代的第n个台阶走法，每一步保存当前climbStairs(n - 1)和climbStairs(n - 2)的结果。
代码
int climbStairs(int n) {
if(n == 1)
return 1;
else if(n == 2)
return 2;
else
{
int fn_2 = 1, fn_1 = 2, count = 0;
for(int i = 3;i <= n; i++)
{
count = fn_1 + fn_2;//累加结果
//向下迭代
fn_2 = fn_1;//下次迭代的第n-2个台阶的走法等于上次迭代n-1个台阶的走法
fn_1 = count;//下次迭代的第n-1个台阶的走法等于上次迭代的第n个台阶走法
}
return count;
// 递归思想 climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)
// return climbStairs(n - 1) + climbStairs(n - 2);
}
}结果
