LeetCode_70_爬楼梯
考察内容：
动态规划
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
示例：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题思路：
这道题目是典型的动态规划类型题目，首先我们要理解动态规划的思想：大事化小，小事化无。将大规模的问题转换为一个个小规模问题，并且保存这些小规模问题的答案，为最后求解大规模问题做准备。
这道题需要反向思考，即从后往前考虑。假设dp[i]表示爬上第 i i i层台阶所有的方案数，根据题目要求，我们一次只能爬1层台阶或者2层台阶。
- 如果我们选择最后一步只爬一层台阶，到达第 i i i层，则这种情况一共有dp[i-1]种方案，因为我们一定是从第 i − 1 i-1 i−1层爬1层台阶上来的，因此有dp[i-1]种方法。
- 如果我们选择最后一步爬两层台阶，到达第 i i i层，同理，这种情况共有dp[i-2]种方案，因为只能在dp[i-2]的每种方案末尾加上2阶才能实现爬两层台阶到达第 i i i层。
所以，由上面的分析我们就可以写出本题的状态转移方程：dp[i] = dp[i-1] + dp[i-2]
C++解题如下：
class solution{
public:
int climbStairs(int n){
vector<int>dp(n+1);//因为题目说n是正整数，而数组下标又从0开始，所以我们让dp数组比n大1
//让dp数组从下标为1开始存储
if(n <= 2){
return n;
}//1层台阶只有1种方法，2层台阶有2种方法，这相当于边界条件
for(int i = 3; i < n + 1 ;i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];//最后返回第n层台阶的所有方案即可。
}
};
我们注意到，其实对于每个 n > 2 n > 2 n>2,它的方案数量都只跟 n − 1 n - 1 n−1与 n − 2 n - 2 n−2有关系，所以我们可以使用滑动窗口的方法使得额外开销从一个大小为 n + 1 n + 1 n+1的数组优化为O(1)
如上图所示，p与q之和是r，在计算一次之后我们可以将第一次的p弹出窗口，将第一次的q放在p的位置，第一次的r放在q的位置，再计算第二个r…以此类推。这就像p、q、r是一个固定的窗口，我们在不断向后滑动它一样。如此一来我们只需要一个大小为3的窗口，而不用创建一个大小为n+1的dp数组了。
class solution{
public:
int climbStairs(int n){
if(n <= 2){
return n;
}
int p = 1, q = 2, r = 0;//初始化滑动窗口
for(int i = 3; i < n; i++){
r = p + q;
p = q;
q = r;//上面动画演示的过程，即窗口滑动的过程
}
return r;
}
};