组成字符串的最小路径

Question

给定一个矩阵 N x M 的符号 S 和一个给定的符号序列，找到以给定顺序遍历所有符号的最小路径。允许的方向是 UP, DOWN, LEFT, RIGHT.

示例：

Matrix:
   123
   265
   346
Sequence:
   1234561
Output:
   8 (start from top left corner, then D, D, R, R, U, L, U, L)

请注意符号可以重复，因此图形算法在这里没有用处。 实际路径不相关，只有数字，因此动态规划可能是要走的路。

形式上：给定的符号序列必须是路径的子序列。

我正在寻找一种算法来找到上述最短路径的长度。

Answer 1

动态规划状态可以是(row, col, pos)：棋盘上的两个坐标和我们构建的序列中的位置。

函数f (row, col, pos)是达到这种状态的最小总行驶距离。

显然，当matrix[row][col]不等于sequence[pos]时，状态无效。我们将通过 f (row, col, pos) = infinity.

对其进行编码

对于 matrix[row][col] = sequence[1].

这样的位置，底数是 f (row, col, 1) = 0

外循环遍历状态的 pos 部分。要在 matrix[row][col] 等于 sequence[pos] 的情况下找到 f (row, col, pos)，我们要观察所有状态 (row', col', pos - 1) 并取 f (row', col', pos - 1) 的最小值加上距离(row', col') 到 (row, col)。这个距离正好是|row - row'| + |col - col'|.

答案是 f (row, col, n) 的最小值，其中 n 是序列的长度。

希望你能从这里开始。

即使实际路径相关，这种方法也会有所帮助。为了找到实际路径，我们可以将先前的状态与函数值一起存储。换句话说，f (row, col, pos) 可以是一个三元组：实际答案，前一个状态的 row'，前一个状态的 col'。

Answer 2

让f(i, j)表示实现序列前缀的最小距离，s，最大长度i，当使用第j个实例时字符矩阵 s[i]。那么：

f(i, j) = min(d(c, j') + f(i - 1, j'))

for all j'

where d is the distance function
      c is the jth instance of the character s[i]
      j' is an instance of the character s[i - 1]

此解决方案的最大复杂度为 O(n * (r * c) * (r * c))，因为序列中有 n 个字符，每个字符最多有 r * c 个实例。但是对于序列中每个字符的矩阵中的实例数相对较小的输入，效率可能会显着提高。

组成字符串的最小路径

Minimal path to form a string

theory

algorithm

dynamic-programming