记忆化搜索可以减少重复计算。

以斐波那契数列为例，简单的递归函数存在大量重复计算，时间复杂度较高，因此可以采用记忆化搜索的算法来提高计算效率。

$ F(0)=1 $
$ F(1)=1 $
$ F(2)=F(1)+F(0) $
$ F(3)=F(2)+F(1) $
$ ... $
$ F(n)=F(n-1)+F(n-2) $

代码如下

Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
keyboard.close();

int[] memorization = new int[n+1];
for (int i = 0; i <= n; i ++) {
    if (i == 0 || i == 1) {
        memorization[i] = 1;
    } else {
        memorization[i] = memorization[i-1] + memorization[i-2];
    }
}

System.out.println(memorization[n]);

---

例1 Function

题目来源：P1464 Function - 洛谷

题目描述

对于一个递归函数 $w(a,b,c)$

• 如果 $a \le 0$ 或 $b \le 0$ 或 $c \le 0$ 就返回值$1$。
• 如果 $a>20$ 或 $b>20$ 或 $c>20$ 就返回 $w(20,20,20)$
• 如果 $a<b$ 并且 $b<c$ 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$。
• 其它的情况就返回 $w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)$

这是个简单的递归函数，但实现起来可能会有些问题。当 $a,b,c$ 均为 $15$ 时，调用的次数将非常的多。你要想个办法才行。

注意：例如 $w(30,-1,0)$ 又满足条件 $1$ 又满足条件 $2$，请按照最上面的条件来算，答案为 $1$。

输入格式

会有若干行。

并以 $-1,-1,-1$ 结束。

保证输入的数在 $[-9223372036854775808,9223372036854775807]$ 之间，并且是整数。

输出格式

输出若干行，每一行格式：

w(a, b, c) = ans

注意空格。

样例 #1

样例输入 #1

1 1 1
2 2 2
-1 -1 -1

样例输出 #1

w(1, 1, 1) = 2
w(2, 2, 2) = 4

题解

import java.util.Scanner;

public class Main {

    static int[][][] w = new int[21][21][21];

    public static void main(String[] args) {

        init();

        Scanner keyboard = new Scanner(System.in);

        int a = keyboard.nextInt();
        int b = keyboard.nextInt();
        int c = keyboard.nextInt();

        while (!(a == b && b == c && a == -1)) {
            if (a < 0 || b < 0 || c < 0) {
                System.out.printf("w(%d, %d, %d) = %d%n", a, b, c, 1);
            } else if (a > 20 || b > 20 || c > 20) {
                System.out.printf("w(%d, %d, %d) = %d%n", a, b, c, w[20][20][20]);
            } else {
                System.out.printf("w(%d, %d, %d) = %d%n", a, b, c, w[a][b][c]);
            }
            a = keyboard.nextInt();
            b = keyboard.nextInt();
            c = keyboard.nextInt();
        }

        keyboard.close();

    }

    public static void init() {

        for (int a = 0; a <= 20; a ++) {
            for (int b = 0; b <= 20; b ++) {
                for (int c = 0; c <= 20; c ++) {
                    if (a == 0 || b == 0 || c == 0) {
                        w[a][b][c] = 1;
                    } else if (a < b && b < c) {
                        w[a][b][c] = w[a][b][c-1] + w[a][b-1][c-1] - w[a][b-1][c];
                    } else {
                        w[a][b][c] = w[a-1][b][c] + w[a-1][b-1][c] + w[a-1][b][c-1] - w[a-1][b-1][c-1];
                    }
                }
            }
        }

    }

}

---

• 分类： 默认分类
• 标签： 笔记 算法