Java中的记忆(Memoization)算法

公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序

腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

Memoization 被很多人翻译成记忆，是根据字面意思来翻译的。今天我就来说一说记忆化算法。

它其实是一种很巧妙的思想或设计，被称为算法，我想主要是因为它经常会和一些算法进行搭配使用吧。

Memoization 应该有很大的使用场景的，举个例子。我们现在要算一个斐波那契数列，对于一个已经算过的数，就没必要再进行计算一遍了。我们可以把这个数之前算过的结果从缓存中取出来。

比如类似下面的斐波那契数列。

0,1,1,2,3,5,8,13,21,34,55,89,144 ..

它们具有以下递归关系：

F（n）= F（n-1）+ F（n-2）

在 Java 中我们可以靠递归函数来实现。

// Fibonacci without Memoization
public int fibonacci(int n){
	
	if( n == 0 ) return 0;
	if( n == 1 ) return 1;
	
	System.out.println("Calculating fibonacci number for: "+n);
	return (fibonacci(n-1) + fibonacci(n-2));	
}

现在，我们可以输入任意数进行计算。但是，当我重复计算一个数时，它并没有记忆，并没有记住上次对该数计算对结果。还是会一层一层的递归计算。

解决这类问题的办法就是，采用缓存，把之前计算过的数字直接缓存起来。下次再调用就先判断缓存中是否有没有，没有的化再计算，否则直接从缓存中读取。

public class FibonacciMemoizationAlgorithm {
	private Map<Integer, Integer> memoizeTable = new HashMap<>(); // O(1)
	// Fibonacci with Memoization
	public int fibonacciMemoize(int n){
		if( n == 0 ) return 0;
		if( n == 1 ) return 1;
		if( this.memoizeTable.containsKey(n) ) {
			System.out.println("Getting value from computed result for "+n);
			return this.memoizeTable.get(n);
		}
		int result = fibonacciMemoize(n-1)+ fibonacciMemoize(n-2);
		System.out.println("Putting result in cache for "+n);
		this.memoizeTable.put(n, result);
		return result;
	}
	// Fibonacci without Memoization
	public int fibonacci(int n){
		if( n == 0 ) return 0;
		if( n == 1 ) return 1;
		System.out.println("Calculating fibonacci number for: "+n);
		return (fibonacci(n-1) + fibonacci(n-2));	
	}
	public static void main(String[] args) {
		FibonacciMemoizationAlgorithm fibonacciAlgorithm = new FibonacciMemoizationAlgorithm();
		System.out.println("Fibonacci value for n=5:  "+fibonacciAlgorithm.fibonacciMemoize(5));
 
	}
}

这就是记忆化的原理，不同的场景采用的缓存技术不同，但原理基本都类似。

最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

本文原文出处：业余草： » Java中的记忆(Memoization)算法