подзадача для последовательной декомпозиции графа

[cooler_3105]

Имеется матрица смежности упорядоченного ориентированного графа (например, размерностью 9*9). 1 соответствует наличию дуги, 0 - ее отсутствием. Нужно вычислить
С(2,1)
С(3,2), С(3,1)
С(4,3), С(4,2), С(4,1)
С(5,4), С(5,3), С(5,2)
...................
С(9,8), С(9,7), С(9,6)
Максимальное кол-во значений С в каждой строке дается в условии (в данном случае макс. кол-во = 3). Т.е. сначала считается одно значение (в нашем случае С(2,1)), потом - 2 (С(3,2), С(3,1)), и т.д. пока не дойдем до макс. кол-ва значений (С(4,3), С(4,2), С(4,1)), которое сохраняется до конца расчетов (С(9,8), С(9,7), С(9,6)).
С высчитывается по формуле: С(x,y) = количеству существующих ребер (i*j) при y<=i<x, j>=x. По матрице смежности
С(x,y) равняется сумме значений матрицы смежности в прямоугольнике шириной (x-y) и длиной до конца матрицы, левый верхний угол которого - ячейка (y,x).
В данном случае нужно явно использовать динамическое программирование. Вопрос в том, как оптимально использовать вычисления, проводимые ранее.
Это является подзадачей при последовательной декомпозиции графа.

[RXL]

cooler_3105, расскажи, что уже придумал.

[cooler_3105]

RXL, я думаю сначала надо вычислить первый столбец, т.е. С(2,1), С(3,2), С(4,3)...С(9,8). Это считается тривиально, С(х,у) = сумме строки матрицы смежности, начиная с элемента a[y][х].
Затем считаем второй стоблец: С(3,1), С(4,2)... С(9,7). Например С(3,1)=С(2,1)+С(3,2) (не забудем проверить элемент [1][2], если он 1, тогда из С(3,1) вычтем единицу). По мере счета второго столбца проверять придется больше элементов (они располагаются в матрице лесенкой).
Затм считаем следующий столбец: С(4,1) = С(4,2)+С(4,3).
Удобно нарисовать матрицу, так становится понятнее.

[cooler_3105]

Прошу модераторов закрыть тему, задача решена.