下面是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];
}

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

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

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

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

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

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);
}

下面是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个数字。这种技术实际上叫做自下而上技术。

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

自顶向下和自底向上DP是解决相同问题的两种不同方法。考虑一个记忆(自顶向下)vs动态(自底向上)编程解决方案来计算斐波那契数。

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

我个人觉得记忆更自然。你可以取一个递归函数，并通过一个机械的过程来记忆它(首先在缓存中查找答案，如果可能的话返回它，否则递归地计算它，然后在返回之前，你把计算保存在缓存中以备将来使用)，而做自底向上的动态编程需要你编码一个计算解决方案的顺序，这样就不会在它所依赖的小问题之前计算“大问题”。

简单地说，自顶向下方法使用递归一次又一次地调用子问题，而自底向上方法使用单个而不调用任何子问题，因此它更有效。