定义：

备忘录方法也用一个表格来保存已解决的子问题的答案，在下次需要解决此问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

UML如下：

具体代码实现：

成绩单：

public class Originator {
private String state;         //成绩
public void setState(String state) {
	this.state = state;
}
public String getState() {
	return state;
}
public Memento Create() {     //创造备忘录
	return new Memento(state);
}
public void SetMemento(Memento memento) {     //还原
	this.state=memento.getState();
}	
public void show() {
	System.out.println("当前分数"+state);
}
}

备忘录：

public class Memento {
public String state;
public Memento(String state) {
	this.state=state;
}
public String getState() {
	System.out.println("正在还原");
	return state;
}
}

管理者：

public class Administration {
private Memento memento;          //备忘录
public void setMemento(Originator originator) {
	this.memento = originator.Create();
}
public Memento getMemento() {
	return memento;
}
}

主方法：

public class Main {

	public static void main(String[] args) {
		Originator originator=new Originator();
		originator.setState("111");
		originator.show();
		Administration a=new Administration();
		a.setMemento(originator);//设置备忘录
		originator.setState("321");;
		originator.show();
		originator.SetMemento(a.getMemento());//还原数据
		originator.show();
        
	}

}

动态规划与备忘录方法的区别（矩阵连乘问题）

动态规划算法的基本要素：
1 最优子结构性质
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2 重叠子问题性质
动态规划算法对每个问题只解一次，将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。
备忘录方法：
•用一个表格来保存已解决的子问题的答案，用的时候查表即可。
•采用的递归方式是自顶向下。
•控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。
•初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。
备忘录方法与动态规划和递归的区别：
1、动态规划是自低向上 ，备忘录方法是自顶向下，递归是自顶向下
2、动态规划每个子问题都要解一次，但不会求解重复子问题；备忘录方法只解哪些确实需要解的子问题；递归方法每个子问题都要解一次，包括重复子问题• 。
矩阵连乘问题基本实现

//备忘录方法
//建立备忘录
	public static int memMatrixChain(int n) {
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				m[i][j]=0;//备忘录先初始化都为0
		return lookupChain(1,n);
	}
	//递归求解问题并先查表
	public static int lookupChain(int i,int j) {
		if(m[i][j]>0) return m[i][j];//先查表，如果对应值不为0说明求解过，直接拿来用
		if(i==j) return 0;
		int u=lookupChain(i+1,j)+p[i-1]*p[i]*p[j];
		s[i][j]=i;
		for(int k=i+1;k<j;k++) {
			int t=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];
			if(t<u) {
				u=t;
				s[i][j]=k;
			}
		}
		m[i][j]=u;//更新备忘录
		return u;
	}

//动态规划
public static String matrixChain(int p[]，int [][]m,int [][]n) {
        int n = p.length - 1;  //为p的实际最大下标
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }
        for (int r = 2; r <= n; r++) // r为当前计算的链长（子问题规模）
        {
            for (int i = 1; i <= n - r + 1; i++)// n-r+1为最后一个r链的前边界
            {
                int j = i + r - 1;// 计算前边界为r，链长为r的链的后边界
                m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];// 将链ij划分为A(i) *( A[i+1:j] )
                s[i][j] = i;
                for (int k = i + 1; k < j; k++) {
                    // 将链ij划分为( A[i:k] )* (A[k+1:j])
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }

在之前的文章中，我们学习了如何用动态规划算法实现矩阵的连乘积问题，由于矩阵连乘积问题具有子问题重叠性，所以采用递归算法求解时有些子问题会被反复计算多次，从而导致效率低下。如果在递归算法中引入二维数组 m[i][j] ，求解子问题后将解储存到 m[i][j] 中，下次可以直接读取使用。这样就可以得到一个基于递归算法的高效方法，即备忘录方法。备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解，需要注意的是，备忘录方法是动态规划算法的变形。

接下来我们用代码实现一下：

//用备忘录方法解决矩阵连乘积问题 

#include<stdio.h>

#define MAX_SIZE 100

int LookupChain(int i, int j, int p[MAX_SIZE], int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE]);
int MemoizedMatrixChain(int n, int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE]);

int MemoizedMatrixChain(int n, int p[MAX_SIZE], int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE])
{
	int i,j;
	//将最少数乘次数矩阵全部初始化为0 
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			m[i][j] = 0;
		}
	}
	return LookupChain(1,n,p,m,s);
}

int LookupChain(int i, int j, int p[MAX_SIZE], int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE])
{
	if ( m[ i ][ j ] > 0 ) 
		return m[ i ][ j ];
	//因为m[i][j]的值位于上三角区域，当i=j时为单一矩阵，无需计算，直接返回0 
  	if ( i == j ) 
	  	return 0;
  	//令k = i，即(i,k)~(k+1,j) 用于计算最小k值 
  	int u = LookupChain( i, i ,p, m, s ) + LookupChain( i + 1, j, p, m, s ) + p[ i - 1 ] * p[ i ] * p[ j ];
  	s[ i ][ j ] = i;
  	//该部分依次断开k=(i+1)~(j-1)，求出s和m 
  	for ( int k = i + 1; k < j; k++ )
  	{
    	int t = LookupChain( i, k ,p, m, s) + LookupChain( k + 1, j ,p, m, s) + p[ i - 1 ] * p[ k ] * p[ j ];
	 	if ( t < u )
    	{ 
      	u = t;
      	s[ i ][ j ] = k;
    	}
  	}
  	m[ i ][ j ] = u;
  	return u;
}

int main()
{
	int p[MAX_SIZE];//矩阵连乘积A1A2...An中矩阵的位数一维数组，其中Ai的维数为Pi-1*Pi，i=1,2,..,n 
	int n;//矩阵个数 
	int m[MAX_SIZE][MAX_SIZE];//最少数乘次数 
	int s[MAX_SIZE][MAX_SIZE];//A[i,j]的 最佳断开位置 
	int i;
	printf("请输入矩阵个数：\n");
	scanf("%d",&n);
	printf("请输入矩阵的维度，如现在有一个10*20，20*30的矩阵，那么P0=10，P1=20，P2=30\n");
	for(i = 0; i <= n; i++)
	{
		scanf("%d",&p[i]);
	}
	int minMuNum = MemoizedMatrixChain( n, p, m, s ); //最少数乘次数 
	printf("%d\n",minMuNum);
} 

这里我们需要注意一点，备忘录方法自顶向下计算，而动态规划算法是由对角线向右上角计算的。

运行结果如下：