Если дан ориентированный невзвешенный граф с вершинами v1, v2,…, vn и без циклов, укажите количество различных путей от v1 до vn.
Используйте одномерную диаграмму, где N [j] - количество различных путей от v1 до vj.С этой идеей N 1 - это число различных путей от v1 до v1, которое является базовым случаем для рекурсии, и принимается равным 1.
a. Выясните и объяснитеключевая рекурсивная идея, а именно, как можно вычислить ячейку N [j], предполагая, что требуемые ячейки N [k] для других вершин vk уже вычислены?Обратите внимание, что ответ должен ссылаться на график.
b. Продемонстрируйте полный алгоритм, заполнив пустую диаграмму динамического программирования, приведенную ниже, используя график график диаграммы