Самая длинная убывающая последовательность элементов в матрице

Question

Я пытаюсь решить проблему, где мне нужно найти самую длинную убывающую последовательность элементов матрицы размера nxn, где последовательность

S = (mi1j1, mi2j2, ·, ·, mikjk)

такой, что

ir mir+1jr+1 для всех 1 ≤ r

, Я не могу думать о том, как подойти к проблеме. Мне нужно применить динамическое программирование к нему. Кто-нибудь может дать мне подсказку о том, как я должен подойти к этой проблеме. (Так как это мой HW, пожалуйста, не дайте точного решения. Я ищу материалы для чтения, используя которые я могу понять эту проблему.)

Answer 1

Идея динамического программного решения довольно проста, и я не думаю, что она требует дополнительного чтения. Предположим, что f(i, j) - длина самой длинной убывающей последовательности, заканчивающейся элементом (i, j). Если значения f вычисляются для всех i, j так, что i

Answer 2

Пусть mi,j=INF-mi,j, где INF - очень большое число:), тогда задача состоит в том, чтобы найти самую длинную возрастающую последовательность, прочитайте этот блог http://codeforces.com/blog/entry/1412