2. На рисунке — схема дорог, связывающих города А, В, С, D, E, F, G, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует разных путей из города А в город Н?

A: 1 путь (начало)
B: 1 путь (из A)
D: 1 путь (из A)
C: Пути из A в C + Пути из B в C = 1 (из A) + 1 (из B) = 2 пути.
E: Пути из B в E + Пути из C в E = 1 (из B) + 2 (из C) = 3 пути.
F: Пути из C в F + Пути из E в F = 2 (из C) + 3 (из E) = 5 путей.
G: Пути из E в G + Пути из F в G = 3 (из E) + 5 (из F) = 8 путей.
H: Пути из G в H + Пути из F в H = 8 (из G) + 5 (из F) = 13 путей.

Question

Вопрос:

Accepted Answer

Для решения этой задачи будем использовать динамическое программирование, подсчитывая количество путей до каждого города.

Ответ: 13