动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在[数学]、[管理科学]、[计算机科学]、[经济学]和[生物信息学]中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
如果要求解一个问题的最优解（通常是求最大值或最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑使用动态规划解决此问题。
动态规划求解问题的特点：
1、求一个问题的最优解；
2、整体问题的最优解是依赖各个子问题的最优解；
3、这些小问题之间还有相互重叠的更小的子问题；
4、从上往下分析问题，从下往上求解问题。

动态规划是自底向上的，递归是自顶向下的。
自底向上是从问题规模最小的f(1)和f(2)开始往上推，直到推到我们想要的答案f(20)。

 public int fib(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }

自顶向下是从一个规模较大的原问题比如f(20)，向下逐层分解，直到f(1)和f(2)触底，然后逐层返回答案。

public int fib(int n) {
    if(n == 1 || n == 2) {
          return n;
    }

    return fib(n-1) + fib(n-2);
}