【算法】备忘录法（记忆化搜索）_备忘录算法

什么是备忘录法

1. 备忘录法是为了解决避免递归算法中相同子问题的重复求解。
2. 备忘录法为每个解过的子问题建立备忘录以备需要时查看，所以也称搜表法。
3. 备忘录法的控制与直接使用递归方法的控制结构相同。
4. 备忘录法又称记忆化搜索，自顶向下的方式解决问题。

备忘录法的实现

1. 避免子问题重复被求解，我们可以定义一个数组，每次要计算一个子问题时，首先从数组中查询这个子问题的解，子问题解没有在数组中，说明没有计算过该子问题，我们可以计算该子问题，并将解放到数组中去，以便下次计算该子问题时，可以直接从数组中拿。

2. 例如整数划分问题：随着划分整数越大，重复的子问题就越多，为了避免子问题重复计算，我们可以在计算整数划分的算法中添加一个二位数组参数，把我们子问题的解放到数组中，例如q（6，3）的解就放到 d [6] [3]中。

代码实现：

public class Demo03 {


    //测试：
    public static void main(String[] args) {

        System.out.println(division(6,6,new int[9][9]));

    }


    public static int division(int m,int n,int[][] d){
        //q(1,n)或q（m,1）==1
        if (m==1 || n==1){
            return 1;
        }

        //q(m,n)=q(n,n)=q(n,n-1) +1
        if (m == n){
            if (d[m][n] == 0) {
                d[m][n] = division(n, n-1, d)+1;
            }
            return d[m][n];
        }


        //m < n  ：q(m,n)=q(m,m)
        if (m < n){
            if (d[m][n] == 0) {
                d[m][n] = division(m, m, d);
            }
            return d[m][n];
        }

        //m>n>1时 q(m,n)=q(m,n-1)+q(m-n,n)
        if (m > n && n >1){
            if (d[m][n] == 0) {
                d[m][n] = division(m, n-1, d)+division(m-n,n,d);
            }
            return d[m][n];
        }

        return 0;
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47