algorithm - 二维格上的字符串匹配

Question

我正在尝试查看一个 n 乘 m 的字符数组，并给定一个长度为 n + m - 1 的输入字符串，我需要检查匹配的最大字符数，因为我们只能去在任何一步向下或向右(单调点阵路径)。

在我看来，这似乎是一个动态规划问题，我在其中查看当前的最佳解决方案，看看是向下匹配还是向右匹配并使其更好，然后将其与某个先前计算的值进行比较(这是我正在努力的地方)。任何见解都会很棒!

Answer 1

使用 n x m 的辅助数组，在每个单元格上存储最大的“匹配”，您可以达到该点。因此，要计算位置 (i,j) 的值，您可以使用 m = MAX([i,j-1]; [i-1,j])因为这是你可能来自的两个可能方向。最后，根据输入矩阵中的 (i,j) 单元格是否与i+ j -1 输入字符串的字符。

可以从左到右，从上到下填充辅助矩阵。总体结果当然会在单元格 (n,m) 中。为了能够重建通向该最大值的路径，您还必须在每个单元格上存储您从中获得最大值的单元格 m(顶部或左侧)。