题目
climbing-stairs
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路
假设楼梯台阶从下到上依次标号为0、1、2、3...n。
用f(x)代表从楼底走到第x阶有多少种方法。
因此，
，
，
递推公式的原因是只能走到台阶x-1或台阶x-2走动台阶x。因此只要计算出f(x-1)和f(x-2)就可以得出f(x)。
递归/回溯
这个递推公式就是斐波那契数列，可以直接写一个递归循环。
递归可以完成题目，但是提交之后会显示超时，因为递归很耗费时间。
时间复杂度是级别的。
c++代码
class Solution {
public:
int climbStairs(int n) {
if(n == 0) return 1;
else if(n == 1) return 1;
else
{
return climbStairs(n-1)+climbStairs(n-2);
}
}
};
记忆化递归
递归方法在进行计算的时候会出现大量重复的计算，因此可以使用数组将每一步的计算结果存储下来，这样下次可以直接使用，节省时间。
时间复杂度：O(n)
空间复杂度：O(n)
c++代码
class Solution {
int a[1000]= {0};
public:
int climbStairs(int n) {
if(n==0||n==1)
{
a[n] = 1;
return 1;
}
if(a[n]>0) return a[n];
a[n] = climbStairs(n-1) + climbStairs(n-2);
return a[n];
}
};
动态规划
先定义dp状态：定义状态dp[i]为走到楼梯i总共可以走的步数。
定义递推公式：dp[i] = dp[i-1] + dp[i-2]
定义初始化变量：dp[0] = 1，dp[1] = 1
c++代码1
使用mem数组来存储计算过的dp状态，返回数组最后的值。
class Solution {
public:
int climbStairs(int n) {
long a[100000];
if(n==0 || n==1) return 1;
a[0] = a[1] = 1;
for(int i=2; i<=n; i++)
{
a[i] = a[i-1] + a[i-2];
}
return a[n];
}
};
c++代码2
不使用数组而是使用两个变量来储存dp[i-1]+dp[i-2]，节省存储空间。
时间复杂度O(n)；
空间复杂度O(1)；
class Solution {
public:
int climbStairs(int n) {
int fn_1 = 1, fn_2 = 1,tmp; //fn_1为dp[i-1]，fn_2为dp[i-2]
int result=0;
if(n==1) return 1;
for(int i=2; i<=n; i++)
{
result = fn_1 + fn_2;
fn_1 = fn_2;
fn_2 = result;
}
return result;
}
};
