青蛙跳台阶问题（动态规划入门/斐波那契数列）
什么是动态规划？
对于很多问题，可以将问题分割成各个子问题，而子问题之间有递推等关系式。
此时我们可以通过已经计算出来的子问题答案来求解当前问题，而无需从头算起。这便称为动态规划。
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
读题思路：
对于该问题，若不了解动态规划相关知识，咋一看毫无头绪，暴力求解直接out of time。
其实题目的切入点在于只能跳1级 or 2级。这是一个很好的限制条件，这说明（n级）问题与（n-1）级问题和（n-2）级问题有关，由此可以退出递推关系式。
若没有此项限制，递推将变得非常复杂，动态规划将会退化为暴力求解，此时则需要数理求解。
显然我们可以得出
f(n) = f(n-1)+f(n-2)
(f(n):跳上一个 n 级的台阶所有的跳法总数。)
代码示例：
class Solution {
public:
int numWays(int n) {
if(n==0) return 1;
if(n==1) return 1;
int pre1 = 1;
int pre2 = 1;
int temp;
for(int i=2;i<=n;i++){
temp = pre1+pre2;
if(temp>1000000007){
temp = temp%1000000007;
}
pre1 = pre2;
pre2 = temp;
}
return pre2;
}
};
上一篇：
通过多线程提高代码的执行效率例子
下一篇：
python两种方法实现线性规划