如何将此递归解决方案转换为记忆的解决方案，以解决最长的常见底带问题？

Question

我能够自己提出递归解决方案，解决了最长的常见子字符串问题：

import static java.lang.Math.max;

public class SolutionRecursive {
    public int longestCommonSubstringLength(String X, String Y) {
        return lcsHelper(X, Y, 1, 1, 0);
    }

    private int lcsHelper(String X, String Y, int xSize, int ySize, int runningSubstringSize) {
        if (xSize > X.length() || ySize > Y.length()) return runningSubstringSize;
        if (X.charAt(xSize - 1) != Y.charAt(ySize - 1)) {
            return max(runningSubstringSize,
                    max(lcsHelper(X, Y, xSize + 1, ySize, 0),
                            lcsHelper(X, Y, xSize, ySize + 1, 0)));
        }
        return lcsHelper(X, Y, xSize + 1, ySize + 1, runningSubstringSize + 1);
    }
}

我对其进行了测试，而且似乎很好，但是我很难记住递归电话。

import java.util.Arrays;

public class SolutionMemoized implements SolutionLCS{
    private final int UNFILLED = Integer.MIN_VALUE;

    public int longestCommonSubstringLength(String X, String Y) {
        int[][][] memo = new int[X.length() + 1][Y.length() + 1][X.length() + 1];
        for (int i = 1; i < X.length() + 1; i++) {
            for (int j = 0; j < Y.length() + 1; j++) {
                Arrays.fill(memo[i][j], UNFILLED);
            }
        }
        int lcs = lcsHelper(X, Y, X.length(), Y.length(), memo, 0);
        return lcs;
    }

    private int lcsHelper(String X, String Y, int xSize, int ySize, int[][][] memo, int runningSubstringSize) {
        if (xSize == 0 || ySize == 0) {
            return runningSubstringSize;
        }
        if (memo[xSize][ySize][runningSubstringSize] != UNFILLED) {
            return memo[xSize][ySize][runningSubstringSize];
        }
        if (X.charAt(xSize - 1) == Y.charAt(ySize - 1)) {
            memo[xSize][ySize][runningSubstringSize] = lcsHelper(X, Y, xSize - 1, ySize - 1, memo,
                    runningSubstringSize + 1);
        } else {
            memo[xSize][ySize][runningSubstringSize] = Math.max(runningSubstringSize,
                    Math.max(
                            lcsHelper(X, Y, xSize - 1, ySize, memo, 0),
                            lcsHelper(X, Y, xSize, ySize - 1, memo, 0)
                    ));
        }
        return memo[xSize][ySize][runningSubstringSize];
    }
}

This apparently fails for longestCommonSubstringLength("KXCGMTMVVGFQQWSPD","JXZADDUKVLQPKUZJZHWSUTPCAFSYAIBJHAMMEGWBTPQELRNKBLDXGUZGCSEC") for which the required answer is 2 but it gives 1. I couldn't find lower length failed tests.

谁能告诉我为什么不起作用？我觉得我的递归和回忆代码之间有清晰的1-1对应关系。

on youtube 我找到了一个修复程序，但作者没有解释他到达了。该修复程序将我的最后几行代码行更改为：

  int s1 = runningSubstringSize;

        if (X.charAt(xSize - 1) == Y.charAt(ySize - 1)) {
            s1 = lcsHelper(X, Y, xSize - 1, ySize - 1, memo,
                    runningSubstringSize + 1);
        }
        int s2 = Math.max(runningSubstringSize,
                Math.max(
                        lcsHelper(X, Y, xSize - 1, ySize, memo, 0),
                        lcsHelper(X, Y, xSize, ySize - 1, memo, 0)
                ));

        return memo[xSize][ySize][runningSubstringSize] = Math.max(s1, s2);

为什么我的解决方案（代码块2）即使它与递归代码之间似乎有1-1对应关系？修复程序如何纠正它？

Answer 1

您添加的修复程序已经使问题很明显：

如果当前字符相等，则贪婪地增加了runningsubstringsize ，并为较小的字符串重复。示例：<代码>（ABDC，AFC）的解决方案简化为（ABD，AF） + 1 的解决方案。

但是，您并不考虑仅减少一个字符串并检查它是否提供更好的解决方案的“正常”方案/流动。从上一个示例中，理想情况下应该是

solution(ABDC, AFC) = max (
    solution(ABD, AFC),
    solution(ABDC, AF),
    solution(ABD, AF) + 1
)

添加的修复程序。在设置回忆表中的更新值之前，它会比较所有方案。