Minimal path to form a string

Question

Given a matrix N x M of symbols S and a given sequence of symbols find the minimal path that traverses all of the symbols in a given order. Allowed directions are UP, DOWN, LEFT, RIGHT.

Example:

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

Please note that symbols can be repeated and thus graph algorithms are of no use here. The actual path is not relevant, only the number, hence dynamic programming is probably the way to go.

Formally: the given sequence of symbols must be a subsequence of the path.

I'm looking for an algorithm that finds the length of the shortest path described above.

Answer 1

The dynamic programming state can be (row, col, pos): the two coordinates on the board and the position in the sequence we build.

The function f (row, col, pos) is the minimum total distance traveled to achieve such state.

Obviously, when matrix[row][col] is not equal to sequence[pos], the state is invalid. We will encode it by f (row, col, pos) = infinity.

The base is f (row, col, 1) = 0 for positions such that matrix[row][col] = sequence[1].

The outer loop goes over the pos part of the state. To find f (row, col, pos) in the case where matrix[row][col] is equal to sequence[pos], we want to observe all states (row', col', pos - 1) and take the minimum of f (row', col', pos - 1) plus the distance from (row', col') to (row, col). This distance is just |row - row'| + |col - col'|.

The answer is the minimum value of f (row, col, n) where n is the length of the sequence.

Hopefully you can take it from here.

---

This approach would help even if the actual path was relevant. To find the actual path, we could store the previous state along with the function value. In other words, f (row, col, pos) can be a triple: actual answer, row' of the previous state, col' of the previous state.

Answer 2

Let f(i, j) represent the minimum distance to achieve the prefix of the sequence, s, up to length i, when using the jth instance in the matrix of the character s[i]. Then:

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]

This solution has maximum complexity of O(n * (r * c) * (r * c)) since there are n characters in the sequence and each has at most r * c instances. But could be significantly more efficient for inputs where the number of instances in the matrix for each character in the sequence is relatively small.