动态规划认为是递归的反向技术，递归的效率低下。
斐波那契数列 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);
}
动态规划版本
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);
}
随着数字增大，效率差距很大。
