Матрица умножения подзадач графа степень вершины

Question

Я изучаю динамическое программирование, и в главе 15.2 Кормена * Алгоритмы читается:

Для умножения цепочки матриц, если бы мы рисовали граф подзадачи, он будет иметь O(n^2) вершин и каждая вершина будет иметь градус не более n - 1, что дает в общей сложности O(n^3) вершин и ребер.

и когда я рисуюграфик n = 4, я получаю:

Но вершина M[1, 4] имеет степень 6> 4 - 1. Что я неправильно понял?

Answer 1

Решение подзадачи должно дать вам решение главной проблемы, хотя, возможно, и не самой лучшей.Таким образом, подзадачей здесь является вычисление двух продуктов, а не одного.Для продукта A1 A2 A3 A4 с n=4 у нас есть три, то есть n-1, подзадачи: (A1, A2 A3 A4), (A1 A2, A3 A4) и (A1 A2 A3, A4).

Редактировать. Книга также гласит:

Таким образом, мы можем построить оптимальное решение экземпляра задачи умножения цепочки матриц, разбивзадача на две подзадачи (оптимально заключив в скобки Ai ... Ak и Ak+1 ... Aj), ...

Итак, подзадача представляет собой вычисление одного продукта, а не двух.Кажется, что либо в книге есть несоответствие в определении подзадачи, либо n-1 границы не верны и должны быть 2(n-1).