动态规划图算法

Question

我目前正在学习动态编程，我无法解决这个问题。有人能给我一个算法吗？：考虑一个有向图G=(V，E)，其中每个边都标有一个字母Sigma的字符，我们指定一个特殊的顶点s作为开始顶点，另一个f作为最后顶点。我们说G接受一个字符串a=a1a2。如果有一条从s到f的n条边的路径，其标号拼写为序列a。设计了一个O((V+E)n)动态规划算法来确定a是否被G接受。

Answer 1

让

first (str) return the first letter of str
Let len(str) return the length of str
Let rem(str) return str with the first character stripped off.

func (str, v1) =
    true if
    len(str)=0 and s == f
        or
    func(rem(str), v2) is true for any v2 such that there exists an edge connecting v1, v2 labeled first(str)

f(str，v)的值可以被记忆以避免不必要的递归调用。