動(dòng)態(tài)規(guī)劃認(rèn)為是遞歸的反向技術(shù)，遞歸的效率低下。

斐波那契數(shù)列? 0? ， 1,2,3,5 ， 8,13,21,34

?

static?long?recurFib(int?n)?

{

if?(n?<?2)

????????return?n;

else

????????return?recurFib(n?-?1)?+?recurFib(n?-?2);

}

?

?

動(dòng)態(tài)規(guī)劃版本?

?

????static?long?iterFib(int?n)

????{

????????int[]?val?=?new?int[n];

????????if?((n?==?1)?||?(n?==?2))

????????????return?1;

????????else

????????{

????????????val[1]?=?1;

????????????val[2]?=?2;

????????????for?(int?i?=?3;?i?<=?n?-?1;?i++)

????????????????val[i]?=?val[i?-?1]?+?val[i?-?2];

????????}

????????return?val[n?-?1];

}

?

static?void?Main()

{

Timing?tObj?=?new?Timing();

????Timing?tObj1?=?new?Timing();

????int?num?=?35;

????long?fibNumber;

????tObj.startTime();

????fibNumber?=?recurFib(num);

????tObj.stopTime();

????Console.WriteLine("Calculating?Fibonacci?number:?"?+?num);

????Console.WriteLine(fibNumber?+?"?in:?"?+?tObj.Result().TotalMilliseconds);

????tObj1.startTime();

????fibNumber?=?iterFib(num);

????tObj1.stopTime();

????Console.WriteLine(fibNumber?+?"?in:?"?+?tObj1.Result().TotalMilliseconds);

}

隨著數(shù)字增大，效率差距很大。