自底向上与自顶向下（递归与动态规划）

从子问题解决原问题, 无非是两种方法，自底向上(Bottom-Up)与自顶向下(Top-Down)，形式上前者对应iteration，利用循环将结果存在数组里，从数组起始位置向后计算；后者对应recursion，即利用函数调用自身实现。如果不存储上一个状态的解，则为递归，否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子：

1) 自底向上

int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
    array[i] = array[i-1] + array[i-2];

这里，为了说明方法，采用数组存储结果，空间复杂度O(n)。事实上，额外空间可以进一步缩小到O(1)：利用几个变量记录之前的状态即可。由于我们记录了子问题的解，故给出的方法就是DP。事实上，自底向上的方式往往都是通过动态编程实现。

2) 自顶向下

int Fibonacci(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

为计算Fibonacci的第n个元素，我们先自顶向下地计算子问题：第n-1个元素和第n-2个元素。由于没有存储子问题的运算结果，我们给出的方法是递归。

递归与动态规划的异同

什么是动态规划