一、动态规划介绍
动态规划 Dynamic Programming，简称 DP，是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。把多阶段问题变换为一系列相互联系的的单阶段问题，然后逐个加以解决。概念中的相互联系，其实指的就是状态转移方程。
很多人觉得DP难，根本原因是因为DP跟一些有固定套路的算法不同（比如DFS、二分法、KMP），它没有实际的步骤规定第一步、第二步来做什么，所以准确来说，DP其实是一种解决问题的思想。
二、题目描述
假设你正在爬楼梯。需要 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 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
三、题目解析
3.1 思路一：通过单阶段之间的关系确定状态转移方程
当做这个题是，我们可以先简单推演一下。由于一次只能上1个或2个台阶，不难发现，假如我当前在第n个台阶上，那么我上一次应该在第n-1个或者第n-2个台阶上。换句话说，当我知道到达第n-1个台阶的方案数f(n-1)，到达第n-2个台阶的方案数是f(n-2)。
那么，我们就自然知道到达第n个阶梯时的方案数，即：f(n)=f(n-1)+f(n-2)，这也被称为此问题的状态转移方程。
当然，我们还需要确定状态转移方程的边界条件。即几种特殊情况：f(0)=0，f(1)=1，f(2)=2；
确定好状态转移方程和边界条件后，就可以开始敲代码了：
class Solution {
public:
int climbStairs(int n) {
int ans = 0;
if(n==0)
return 0;
else if(n==1)
return 1;
else if(n==2)
return 2;
else
return climbStairs(n-1)+climbStairs(n-2);
}
};
这是一个不断的迭代过程，在实际的提交过程中，很可能超过时间限制。
3.2 思路二：数学归纳法
如果觉得很难直接去找到单阶段问题间的关系，也换一种思考方式。通过数学归纳法来推理出隐藏的状态转移方程。
在不清楚单阶段之间的关系的时候，可以正向推演一遍，可以得到如下表所示的数据： | n | 1 | 2 |3 | 4 | 5 | 6 | ... | | :------------: | :------------: | :------------: | :------------: | :------------: | :------------: | :------------: | :------------: | | f(n) | 1 | 2 |3 |5 | 8 | 13 | ... |
通过观察f(n)的变换，想必大家已经看出了规律。即，前两数之和为第三数的值。
由此，我们就可以写代码啦：
class Solution {
public:
int climbStairs(int n) {
int f1=0, f2=1, ans=2;//初始化
if(n==1)
return 1;
else if(n==2)
return 2;
else{
for(int i=1; i<n-1; ++i){
f1 = f2;
f2 = ans;
ans = f1 + f2;
}
return ans;
}
}
};
代码提交结果： 
