Алгоритм динамического программирования графа

Question

В настоящее время я изучаю динамическое программирование, и я не могу понять эту проблему. Может ли кто-нибудь дать мне алгоритм для этого? Рассмотрим ориентированный граф G = (V,E), где каждое ребро помечено символом из алфавита Sigma, и мы обозначим специальную вершину s в качестве начальной, а другую f в качестве конечной. Мы говорим, что G принимает строку A = a1a2 .,, a если существует путь от 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) можно запомнить, чтобы избежать ненужных рекурсивных вызовов.