Java 中的记忆(1D、2D 和 3D)动态编程
记忆是一种基于动态编程的技术，用于通过确保该方法不会对同一组输入运行多次来提高递归算法的性能，方法是保留所提供输入的结果记录(存储在数组中)。可以通过实施自上而下的递归方法来实现记忆。
让我们借助基本的斐波那契示例来理解这种情况
1-D 记忆
我们将考虑一个只有一个非常量参数的递归算法(只有一个参数会改变其值)，因此这种方法称为 1-D 记忆。以下代码用于查找斐波那契数列中的第 N 个(直到 N 的所有项)。
示例
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("计算斐波那契数: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}
输出
如果我们以 n=5 运行上述代码，它将生成以下输出。
计算斐波那契数:5 计算斐波那契数:4 计算斐波那契数:3 计算斐波那契数:2 计算斐波那契数:2 计算斐波那契数:3 计算斐波那契数:2
n=5 的斐波那契值:5
值得注意的是，2 和 3 的斐波那契数被计算了不止一次。让我们通过为上述条件(即 n=5)的斐波那契数列绘制一个递归树来更好地理解。
这里节点的两个子节点将代表它所做的递归调用。可以看出，F(3) 和 F(2) 计算了多次，可以通过在每一步之后缓存结果来避免。
我们将使用实例变量 memoize Set 来缓存结果。首先检查 n 是否已存在于 memoize Set 中，如果是，则返回该值，如果不存在，则计算该值并将其添加到集合中。
示例
import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
private Map<Integer, Integer> memoizeSet = new HashMap<>(); // O(1)
public int fibMemoize(int input) {
if (input == 0)
return 0;
if (input == 1)
return 1;
if (this.memoizeSet.containsKey(input)) {
System.out.println("Getting value from computed result for " + input);
return this.memoizeSet.get(input);
}
int result = fibMemoize(input - 1) + fibMemoize(input - 2);
System.out.println("Putting result in cache for " + input);
this.memoizeSet.put(input, result);
return result;
}
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) {
TutorialPoint tutorialPoint = new TutorialPoint();
System.out.println("Fibonacci value for n=5: " + tutorialPoint.fibMemoize(5));
}
}
输出
如果我们运行上述代码，它将生成以下输出
Adding result in memoizeSet for 2 Adding result in memoizeSet for 3 Getting value from computed result for 2 Adding result in memoizeSet for 4 Getting value from computed result for 3 Adding result in memoizeSet for 5
n=5 的斐波那契值:5
可以看出，2 和 3 的斐波那契数没有重新计算。这里我们引入了一个 HashMap 来存储已经计算的值，这些值在每次斐波那契计算之前都会在集合中检查输入的值是否已经计算过，如果没有，则将特定输入的值添加到集合中。
2-D 记忆
上面的程序只有一个非常量参数。在下面的程序中，我们将以一个有两个参数的递归程序为例，该程序在每次递归调用后都会改变其值，我们将对这两个非常量参数实现记忆以对其进行优化。这称为 2-D 记忆。
例如:-我们将实现标准最长公共子序列(LCS)。如果给出了一组序列，最长公共子序列问题就是找到所有序列中最大长度的公共子序列。可能的组合将是 2n。
示例
class TP {
static int computeMax(int a, int b) {
return (a > b) ? a : b;
}
static int longestComSs(String X, String Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + longestComSs(X, Y, m - 1, n - 1);
else
return computeMax(longestComSs(X, Y, m, n - 1), longestComSs(X, Y, m - 1, n));
}
public static void main(String[] args) {
String word_1 = "AGGTAB";
String word_2 = "GXTXAYB";
System.out.print("Length of LCS is " + longestComSs(word_1, word_2, word_1.length(),word_2.length()));
}
}
输出
如果我们运行上述代码，它将生成以下输出
Length of LCS is 4
在上述半程递归树中，lcs("AXY", "AYZ") 被求解多次。
由于该问题的重叠子结构特性，可以使用记忆或制表来避免预先计算相同的子问题。
递归代码的记忆方法实现如下。
示例
import java.io.*;
import java.lang.*;
class testClass {
final static int maxSize = 1000;
public static int arr[][] = new int[maxSize][maxSize];
public static int calculatelcs(String str_1, String str_2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (arr[m - 1][n - 1] != -1)
return arr[m - 1][n - 1];
if (str_1.charAt(m - 1) == str_2.charAt(n - 1)) {
arr[m - 1][n - 1] = 1 + calculatelcs(str_1, str_2, m - 1, n - 1);
return arr[m - 1][n - 1];
}
else {
int a = calculatelcs(str_1, str_2, m, n - 1);
int b = calculatelcs(str_1, str_2, m - 1, n);
int max = (a > b) ? a : b;
arr[m - 1][n - 1] = max;
return arr[m - 1][n - 1];
}
}
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
arr[i][j] = -1;
}
}
String str_1 = "AGGTAB";
String str_2 = "GXTXAYB";
System.out.println("Length of LCS is " + calculatelcs(str_1, str_2, str_1.length(),str_2.length()));
}
}
输出
如果我们运行上述代码，它将生成以下输出
Length of LCS is 4
方法
我们已经看到，在方法 (calculatelcs) 中有 4 个参数，其中 2 个是常量(不影响记忆)，2 个非常量参数 (m 和 n) 在每个递归方法调用中都会改变其值。因此，为了实现记忆，我们引入了一个二维数组，用于将 lcs(m,n) 的计算值存储在 arr[m-1][n-1] 中。每当再次调用具有相同参数 m 和 n 的函数时，我们不再执行任何递归调用并返回 arr[m-1][n-1]，因为 lcs(m, n) 的先前计算已经存储在 arr[m-1][n-1] 中，从而最大限度地减少了递归调用的次数。
3-D 记忆
这是一种实现具有 3 个非常量参数的递归程序记忆的方法。这里我们以计算三个字符串的 LCS 长度为例。
这里的方法是为给定的字符串生成所有可能的子序列(可能子序列总数为 3ⁿ)并匹配它们之间的最长公共子序列。
我们将引入一个 3-D 表来存储计算值。考虑子序列。
A1[1...i] i < N
A2[1...j] j < M
A3[1...k] k < K
如果我们找到一个共同字符(X[i]==Y[j]==Z[k])，我们需要递归剩余的字符。否则，我们将计算以下情况的最大值
让 X[i] 为其他字符递归
让 Y[j] 为其他字符递归
让 Z[k] 为其他字符递归
因此，如果我们将上述想法公式化为递归函数，则
f(N,M,K)={1+f(N-1,M-1,K-1)if (X[N]==Y[M]==Z[K]maximum(f(N-1,M,K),f(N,M-1,K),f(N,M,K-1))
f(N-1,M,K) = 让 X[i] 为其他项重复
f(N,M-1,K) = 让 Y[j] 为其他项重复
f(N,M,K-1) = 让 Z[k] 为其他项重复
示例
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
class testClass {
public static int[][][] arr = new int[100][100][100];
static int calculatelcs(String str_1, String str_2, String str_3, int m, int n, int o) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
arr[i][j][0] = 0;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= o; j++) {
arr[0][i][j] = 0;
}
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= o; j++) {
arr[i][0][j] = 0;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= o; k++) {
if (str_1.charAt(i - 1) == str_2.charAt(j-1) && str_2.charAt(j1) == str_3.charAt(k-1)) {
arr[i][j][k] = 1 + arr[i - 1][j - 1][k - 1];
}
else {
arr[i][j][k] = calculateMax(arr[i - 1][j][k], arr[i][j - 1][k], arr[i][j][k - 1]);
}
}
}
}
return arr[m][n][o];
}
static int calculateMax(int a, int b, int c) {
if (a > b && a > c)
return a;
if (b > c)
return b;
return c;
}
public static void main(String[] args) {
String str_1 = "clued";
String str_2 = "clueless";
String str_3 = "xcxclueing";
int m = str_1.length();
int n = str_2.length();
int o = str_3.length();
System.out.print("Length of LCS is " + calculatelcs(str_1, str_2, str_3, m, n, o));
}
}
输出
如果我们运行上述代码，它将生成以下输出
Length of LCS is 4
