|
有这么一题 有一个楼梯总共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),推出特征方程 吸了根烟，长长叹了口气，默默的推着三轮车走了。 过了几天，大牛小牛回来了，本想瞻仰一下，自己的代码，是何等的牛B,回温一下当时的成就感。当他们看到 这些公式，什么递归，什么动态规划，在公式面前显示如此苍白，只留下一脸忙然~~ |
|
|
