最长递减的元素序列中的矩阵

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