最長遞減的元素序列中的矩陣

Question

我試圖解決，我需要找到大小爲n×n，其中序列

S =（mi1j1，mi2j2的矩陣的元素的最長下降序列的問題， ···，mikjk）

這樣 即

IR < IR + 1，JR < JR + 1，和mirjr> MIR + 1JR + 1對於所有1個≤[R < k

。我無法想出如何解決這個問題。我需要對其應用動態編程。 任何人都可以給我一個提示，我該如何解決這個問題。 （因爲這是我的HW所以大家以後不要給出確切的解決方案。我找的使用，我可以理解這個問題閱讀材料。）

Answer 1

動態編程解決方案的想法很簡單，我不認爲它需要任何額外的閱讀。假設f（i，j）是以（i，j）元素結尾的最長遞減序列的長度。如果對於所有i，j計算f的值，使得i（ik，jk）很容易計算。所以可以迭代計算答案（按i和j的遞增順序）。

Answer 2

讓mi，j = INF-mi，j，其中INF-非常大的數字:)，然後任務是找到時間最長的序列，讀博客http://codeforces.com/blog/entry/1412