Matematicki problem

[filmil]

Други метод је мало сложенији. Заснива се на парцијалном решавању.

Да би решио проблем за матрицу [(0,0),(m,n)] треба прво да га решиш за матрице: [(0,0),(m,n)], [(0,0),(m-1,n)], [(0,0),(m,n-1)] и [(0,0),(m-1,n-1)].

То значи да треба да кренемо са решавањем од [(0,0),(1,1)] и да радимо ка већим матрицама.

За сваку матрицу коју испиташ, памтиш следеће: листу максималних пуних матрица дотад откривених; листу максималних пуних матрица дотад откривених, које се наслањају на доњу ивицу подматрице; и листу максималних пуних матрица које се наслањају на десну ивицу подматрице.

Ове листе могу инкрементално да се праве на основу претходно израчунатих матрица. На пример, на основу срачунатих листа за [(0,0),(p,q)], можеш да срачунаш листе за [(0,0),(p+1,q)] и [(0,0),(p,q+1)]. Листе са „ослоњеним“ подматрицама требају ти, јер то су једине које могу да „порасту“ додавањем једног додатног реда или колоне на постојећу подматрицу.

Оне могу да „порасту“ додавањем пуне подматрице-колоне или подматрице-реда, које имају одговарајуће димензије. За проверу да ли су подматрица-колона одн. подматрица ред пуни, можеш да користиш предикат из претходне поруке.

Када цео рачун одвртиш до [(0,0),(m,n)], листа максималних матрица имаће само један елемент (по услову ког си навео) и тај елемент је решење.

ф

[dee]

drugi nisam bas razumio, ali prvi mi je vise manje jasan i cini mi se sasvim dovoljan.


puno ti hvala!