algorithm - 组成字符串的最小路径

Question

给定一个由符号 S 组成的矩阵 N x M 和一个给定的符号序列，找到以给定顺序遍历所有符号的最小路径。允许的方向是 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'以前的状态。