动态规划问题可以使用自底向上或自顶向下的方法来解决。

通常，自底向上方法使用制表技术，而自顶向下方法使用递归(带记忆)技术。

但是您也可以使用下面所示的递归使用自底向上和自顶向下的方法。

自底向上:从基本条件开始，递归地传递计算到现在的值。一般来说，这些是尾部递归。

int n = 5;
fibBottomUp(1, 1, 2, n);

private int fibBottomUp(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibBottomUp(j, i + j, count + 1, n);
}

自顶向下:从最后一个条件开始，递归地得到它的子问题的结果。

int n = 5;
fibTopDown(n);

private int fibTopDown(int n) {
    if (n <= 1) return 1;
    return fibTopDown(n - 1) + fibTopDown(n - 2);
}

动态规划通常被称为记忆!

1.记忆是一种自顶向下的技术(通过分解来解决给定的问题)，而动态规划是一种自底向上的技术(从微不足道的子问题开始解决，向上到给定的问题)

2.DP通过从基本情况开始并向上工作来找到解决方案。DP解决了所有的子问题，因为它是自下而上的

不像Memoization，它只解决所需的子问题

DP具有将指数时间暴力解转换为多项式时间算法的潜力。 DP可能更有效，因为它是迭代的

相反，Memoization必须支付由于递归而产生的开销(通常很重要)。

更简单地说，Memoization使用自顶向下的方法来解决问题，即从核心(主要)问题开始，然后将其分解为子问题，并以类似的方式解决这些子问题。在这种方法中，同一子问题可能会多次出现，消耗更多的CPU周期，从而增加时间复杂度。而在动态规划中，同一子问题不会求解多次，而是利用其先验结果来优化解。

动态规划的一个关键特征是存在重叠的子问题。也就是说，您要解决的问题可以分解为子问题，而这些子问题中的许多都具有子问题。这就像“分而治之”，但你最终会做同样的事情很多很多次。我在2003年教授或解释这些问题时用过一个例子:你可以递归地计算斐波那契数。

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

Use your favorite language and try running it for fib(50). It will take a very, very long time. Roughly as much time as fib(50) itself! However, a lot of unnecessary work is being done. fib(50) will call fib(49) and fib(48), but then both of those will end up calling fib(47), even though the value is the same. In fact, fib(47) will be computed three times: by a direct call from fib(49), by a direct call from fib(48), and also by a direct call from another fib(48), the one that was spawned by the computation of fib(49)... So you see, we have overlapping subproblems.

好消息:不需要多次计算相同的值。计算一次后，缓存结果，下次使用缓存的值!这就是动态规划的本质。你可以称之为“自上而下”，“记忆化”，或者其他你想要的名字。这种方法非常直观，也很容易实现。只需首先编写递归解决方案，在小型测试中测试它，添加内存(缓存已经计算的值)，然后——对了!——你完蛋了。

通常你也可以编写一个等效的迭代程序，从下往上工作，没有递归。在这种情况下，这将是更自然的方法:循环从1到50计算所有的斐波那契数。

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

In any interesting scenario the bottom-up solution is usually more difficult to understand. However, once you do understand it, usually you'd get a much clearer big picture of how the algorithm works. In practice, when solving nontrivial problems, I recommend first writing the top-down approach and testing it on small examples. Then write the bottom-up solution and compare the two to make sure you are getting the same thing. Ideally, compare the two solutions automatically. Write a small routine that would generate lots of tests, ideally -- all small tests up to certain size --- and validate that both solutions give the same result. After that use the bottom-up solution in production, but keep the top-bottom code, commented out. This will make it easier for other developers to understand what it is that you are doing: bottom-up code can be quite incomprehensible, even you wrote it and even if you know exactly what you are doing.

在许多应用程序中，由于递归调用的开销，自底向上方法略快一些。在某些问题中，堆栈溢出也可能是一个问题，请注意，这在很大程度上取决于输入数据。在某些情况下，如果您不够了解动态编程，您可能无法编写导致堆栈溢出的测试，但总有一天这种情况仍会发生。

Now, there are problems where the top-down approach is the only feasible solution because the problem space is so big that it is not possible to solve all subproblems. However, the "caching" still works in reasonable time because your input only needs a fraction of the subproblems to be solved --- but it is too tricky to explicitly define, which subproblems you need to solve, and hence to write a bottom-up solution. On the other hand, there are situations when you know you will need to solve all subproblems. In this case go on and use bottom-up.

我个人会使用自上而下的段落优化，也就是换行优化问题(查找Knuth-Plass换行算法;至少TeX使用它，Adobe Systems的一些软件使用类似的方法)。我会用自底向上的快速傅里叶变换。

下面是DP为基础的解决方案的编辑距离问题，这是自上而下的。我希望它也能帮助你理解动态规划的世界:

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

你可以想象它在你家里的递归实现。如果你以前没有解决过类似的问题，这是非常好的和具有挑战性的。

让我们以斐波那契数列为例

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

换句话说，

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

对于前5个斐波那契数

Bottom(first) number :1
Top (fifth) number: 5 

下面以递归斐波那契数列算法为例

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

现在如果我们用下面的命令执行这个程序

rcursive(5);

如果我们仔细研究算法，为了生成第五个数字，它需要第3和第4个数字。所以我的递归实际上是从top(5)开始，然后一直到bottom/lower numbers。这种方法实际上是自顶向下的方法。

为了避免多次进行相同的计算，我们使用动态编程技术。我们存储先前计算的值并重用它。这种技巧叫做记忆。动态规划中除了记忆之外还有更多的内容，在这里不需要讨论。

自顶向下

让我们重写原始算法并添加记忆技术。

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

我们像下面这样执行这个方法

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

这个解决方案仍然是自顶向下的，因为算法从顶部值开始，每一步都从底部得到我们的顶部值。

自底向上

但问题是，我们能不能从底部开始，比如从第一个斐波那契数开始，然后向上走。我们用这个技巧重写一下，

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

现在，如果我们研究这个算法，它实际上是从较低的值开始，然后向上。如果我需要第5个斐波那契数，我实际上是在计算第1个，然后是第二个，然后是第三个，一直到第5个数字。这种技术实际上叫做自下而上技术。

最后二，算法完全满足动态规划的要求。但一个是自上而下的，另一个是自下而上的。两种算法具有相似的空间复杂度和时间复杂度。

没什么好困惑的……你通常以自底向上的方式学习语言(从基础到更复杂的东西)，并经常以自顶向下的方式进行项目(从代码的总体目标和结构到某些实现部分)。