程序员当你觉得是大牛的时候，可以过来看看，分分钟被秒杀，做人一定要低调。

有这么一题
有一个楼梯总共n个台阶，只能往上走，每次只能上1个、2个台阶，总共有多少种走法。
小牛的程序员想了想：
解决方案：
dp[n] 表示n个台阶的走法，那么有：
dp[n]=dp[n-1]+dp[n-2]；
dp[1]=1;dp[2]=2;
这能难到我，

int stepNumer(int n)
{
    if (n < 3)
   		return n;
    else
        return stepNumer(n - 1) + stepNumer(n - 2);
}

大神级别的程序员来了
一看，随着n数一直增长，大量重复的计算，使得复杂度呈指数爆炸增长。
你的递归算法,时间复杂性，随着n的增加，一直爆表。
看我的,动态规划的算法 通过牺牲空间复杂度来换取时间复杂度的降低。

int stepNumer(int n)
{
    int step1 = 1;     
    int step2 = 2;    
    int stepN = 0;
    for (int i = 2;i < n;i++)
    {
        tempN = step1 + step2 ;  
        step1  = step2 ;       
        step2 = tempN ;       
    }
    return n<3?n:tempN;

然后点评了一下：每个f(n)只需计算一次然后记录下来，避免了大量重复的计算
动态规划通过牺牲空间复杂度来换取时间复杂度的降低，单大多情况下牺牲是值得的。
小子你的算法不错，不过还是嫩了点，再好好干几年，修行一下。
然后满意的走了，一天的心情很是高兴。

突然有一天，在地摊卖菜，原本是数学系，出了社会没找到工作，看到这题，不懂代码，随手写了写。
dp[n]=dp[n-1]+dp[n-2]；
dp[1]=1;dp[2]=2;
根据f(n)=f(n-1)+f(n-2),推出特征方程
$x^2=x+1;$x2=x+1;
$(x-\frac{1}{2})^2=\frac{5}{4}$(x−21​)2=45​
推出两值:$x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}$x1​=21+5​​,x2​=21−5​​
根据 特征公式，必然存在a,b使得,
$f(n)=a*x_1^n+b*x_2^n$f(n)=a∗x1n​+b∗x2n​
将f(1)=1,f(2)=2代入公式:
$1=a*(\frac{1+\sqrt{5}}{2})^1+b*(\frac{1-\sqrt{5}}{2})^1$1=a∗(21+5​​)1+b∗(21−5​​)1
$2=a*(\frac{1+\sqrt{5}}{2})^2+b*(\frac{1-\sqrt{5}}{2})^2$2=a∗(21+5​​)2+b∗(21−5​​)2
推算出
$a=\frac{5+\sqrt{5}}{10}，b=\frac{5-\sqrt{5}}{10}$a=105+5​​，b=105−5​​
最后
$f(n) = \frac{5+\sqrt{5}}{10}(\frac{1+\sqrt{5}}{2})^n+\frac{5-\sqrt{5}}{10}(\frac{1-\sqrt{5}}{2})^n$f(n)=105+5​​(21+5​​)n+105−5​​(21−5​​)n
吸了根烟，长长叹了口气，默默的推着三轮车走了。
过了几天，大牛小牛回来了，本想瞻仰一下，自己的代码，是何等的牛B,回温一下当时的成就感。当他们看到
这些公式，什么递归，什么动态规划，在公式面前显示如此苍白，只留下一脸忙然~~