@TOC
1 题目
假设你正在爬楼梯。需要 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 阶2 思路
动态规划 O(n)
状态表示：
f[i] 表示爬到第i个台阶的方法数，那么f[n]就代表爬到楼顶的方法数。
状态计算
因为每一次爬楼梯都有两种选择，一种是爬1阶，一种是爬两阶，所以到第i个台阶有两种方案：
- 由第==i-1==个台阶走到第==i==个台阶。
- 由第==i-2==个台阶走到第==i==个台阶。
边界
到第==一==个台阶只能有一种方案，即爬==一阶==。
到第==二==个台阶有两种方案，既==一次爬两阶==，或者是==爬两次一阶==。
递归
递归思路
当走到第n阶台阶时，不知道有多少种方法，可以往前退，去找第==n-1==个台阶的方法数和第==n-2==个台阶的方法数之和即为第==n==阶台阶的方法数。
终止条件
- ==n=1==时返回==1==
- ==n=2==时返回==2==
BUT
仅仅使用这种递归的话不出意外肯定要==超时==，因为每次计算一次n的方案数都要从n一直循环找到1或2才停止，造成时间上以及空间上都是极大的浪费。所以我们可以怎么做才能不超时且时间复杂度为 O(n) 呢？
答案是使用==记忆化搜索==。
记忆化搜索 O(n)
记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量。
- 首先使用一个表来记录已经存储下的搜索结果，一般用hash表来实现。
- 在每一状态搜索的开始，高效的使用hash表来检验这个状态是否出现过，如果已经出现过，直接调用答案，然后进行回溯。如果没有，则继续搜索。
小提示
记忆化搜索时类似于动态规划的，不同的时，它是倒做的“==递归式动态规划=="。
3 代码
动态规划
class Solution
{
public:
int climbStairs(int n)
{
int dp[1000];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
};记忆化搜索
class Solution {
public:
int f[50];
int climbStairs(int n) {
if (f[n])
return f[n];
else
{
if (n == 1)
return 1;
else if (n == 2)
return 2;
else
return f[n] = climbStairs(n - 1) + climbStairs(n - 2);
}
}
};原题链接 70. 爬楼梯
