memoization：让递归算法更高效
Memoization是一种实现动态编程以使递归算法高效的技术。它通常具有与常规动态编程相同的好处，而无需对原始更自然的递归算法进行重大更改。
基本理念
首先要设计自然递归算法。
如果重复进行具有相同参数的递归调用，则可以通过将这些子问题解决方案保存在表中来记忆低效的递归算法，这样就不必重新计算它们。
履行
为了实现对递归算法的记忆，使用子问题解决方案维护表，但是在递归算法的正常执行期间发生用于填充表的控制结构。这可以通过以下步骤进行总结：
memoized递归算法在表中维护一个条目（数组或对象），用于解决每个子问题的解决方案，每个表条目最初都包含一个特殊值，这表示该条目尚未填写。首次遇到子问题时，会计算其解决方案并将其存储在表中。随后，查找该值而不是计算该值。
为了说明上面的步骤，我们举一个用递归算法计算第n个Fibonacci数列的例程：
// without memoization
static int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n - 1) + fib(n - 2);
}
上述算法的运行时间大致为O(2n)。 这可以在fib(5)中实现可视化，如下图所示：
memoization
在上面的树中，你可以看到重复计算相同的值（例如fib(1)，fib(0)..）。 实际上，每次我们计算fib(i)时，都可以缓存此结果并在以后使用它。 所以，当我们调用fib（n）时，我们不应该做多于0（n）次调用，因为只能在fib（n）处抛出O（n）个可能的值。
// memoized version
static int fibonacciMemo(int n) {
// entry table to cache the computed values
// 用来存储缓存的数组
int[] fibs = new int[n + 1];
// initialize entry table with -1 to say value has to calculated
// 用-1初始化条目表来表示必须计算的值
Arrays.fill(fibs, -1);
return fib(n, fibs);
}
static int fib(int n, int[] fibs) {
if (n == 0 || n == 1) return n;
if (fibs[n] == -1) {
fibs[n] = fib(n - 1, fibs) + fib(n - 2, fibs);
}
return fibs[n];
}
我们可以看到，只需对代码进行一次小修改就可轻松实现此功能，以便在O(n)时间内运行。
优点
这个算法不必转换为迭代算法。它通常提供与通常的动态编程方法相同（或更好）的效率。
为了计算第45个Fibonacci数列，我的机器（i7 Octa-core）需要花费5136ms：
long startTime = System.currentTimeMillis();
System.out.println(fib(45));
System.out.println("Time taken (w/o memo): " + (System.currentTimeMillis() - startTime) + " ms");
但是通过Memoization，它通过0毫秒即可完成。此方法有时也称为自上而下动态编程。
这对于迭代算法的高效详细地址而言，确是一件很酷的事儿。
上面所讨论的源代码都可以在GitHub上找到。
地址：https://github.com/YogenRaii/java-core/tree/master/src/main/java/com/eprogrammerz/examples/algorithm/memoization