Сколько существует различных путей из города A в город H?

Для нахождения количества путей из города A в город H воспользуемся методом динамического программирования. Будем подсчитывать количество путей в каждую вершину на основе количества путей в вершины, из которых можно попасть в данную. Обозначим количество путей в вершину X через P(X): - P(A) = 1 (начальная точка) - P(B) = P(A) = 1 - P(C) = P(A) = 1 - P(D) = P(A) + P(B) = 1 + 1 = 2 - P(E) = P(B) = 1 - P(F) = P(E) + P(D) = 1 + 2 = 3 - P(G) = P(D) + P(C) = 2 + 1 = 3 - P(H) = P(F) + P(G) = 3 + 3 = 6 Таким образом, количество различных путей из города A в город H равно 6.