使用动态编程查找最大尺寸的排序子矩阵

Question

我想解决一个动态编程问题，它包含一个矩阵，找到最大尺寸的排序子矩阵。

我想使用dinamic编程来找到解决方案，但我没有得到正确的结果。我的程序由两种方法组成：第一种方法递归地检查元素附近的位置到参数给定的位置。然后，在第二种方法中，我调用前一个来查找子矩阵的最大顺序，但它不返回正确的结果。

例如，对于这个矩阵，并呼吁用新的解决方案类（5,6）

   10, 1, 4, 1, 4, 0 
       1, 2, 10, 6, 2, 1 
       6, 7, 20, 10, 1, 2 
       9, 10, 23, 0, 3, 5 
       10, 11, 24, 1, 0, 2 

它应该返回4. 这里是我的代码：

import java.util.Scanner; 

public class Solution { 
    private int[][] mat; 
    Scanner sc = new Scanner(System.in); 
    int n, m; 


    public Solution(int n, int m) { 
     this.n = n; 
     this.m = m; 
     mat = new int[n][m]; 
     for(int i = 0; i < n; i++) 
      for(int j = 0; j < m; j++) 
       mat[i][j] = sc.nextInt(); 
     for(int i = 0; i < n; i++) { 
      System.out.println(); 
      for(int j = 0; j < m; j++) 
       System.out.print(mat[i][j] + "\t"); 
     } 
    } 

    public void call() { 
     int sol = maxSortedMatrix(mat); 
     System.out.println("Matrix of order " + sol); 
    } 

    private int nearElements(int i, int j, int[][] mat, int[][] maxLongi) { 
     // basically recursively check surrounding elements. If they are exist and smaller than 
     // current element, we should consider it as the longest increasing sub sequence. However if we 
     // already check one element, the value corresponding to that index pair should no longer be zero, 
     // thus no need to recursively calculate that value again. 
     if (maxLongi[i][j] == 0) { 
     // have not been visited before, need recursive calculation 
      // have not recursively checking. 
      int length = 1; 
      // up 
      if (i - 1 > -1 && mat[i][j] > mat[i - 1][j]) { 
       length = Math.max(length, 1 + nearElements(i - 1, j, mat, maxLongi)); 
      } 
      // down 
      if (i + 1 < mat.length && mat[i][j] > mat[i + 1][j]) { 
       length = Math.max(length, 1 + nearElements(i + 1, j, mat, maxLongi)); 
      } 
      // left 
      if (j - 1 > -1 && mat[i][j] > mat[i][j - 1]) { 
       length = Math.max(length, 1 + nearElements(i, j - 1, mat, maxLongi)); 
      } 

      // right 
      if (j + 1 < mat[0].length && mat[i][j] > mat[i][j + 1]) { 
       length = Math.max(length, 1 + nearElements(i, j + 1, mat, maxLongi)); 
      } 
      maxLongi[i][j] = length; // setting maxLenTailing value here to avoid additional recurssively checking 
      return length; 
     } 
     return maxLongi[i][j]; 
    } 

    private int maxSortedMatrix(int[][] mat) { 
     if (mat == null || mat.length == 0 || mat[0] == null || mat[0].length == 0) { 
      return 0; 
     } 
     int[][] maxLength = new int[n][m]; 
     // store the max length of increasing subsequence that ending at i and j. 
     int max = 0; 
     // top left to bottom right 
     for (int i = 0; i < n; ++i) { 
      for (int j = 0; j < m; ++j) { 
// scan every element in the matrix. 
       maxLength[i][j] = nearElements(i, j, mat, maxLength); 
       max = Math.max(max, maxLength[i][j]); 
      } 
     } 
     return max; 
    } 
} 

Answer 1

方形子矩阵的答案可能比计算要简单一点一般的矩形。在Python中，我们可以利用双比较的小动作（请参阅ruakh的回答进行一般性讨论）：

a = [ 
    [10, 1, 4, 1, 4, 0], 
    [ 1, 2,10, 6, 2, 1], 
    [ 6, 7,20,10, 1, 2], 
    [ 9,10,23, 0, 3, 5], 
    [10,11,24, 1, 0, 2] 
] 

m = [ [1] * len(a[0]) for i in range(0,len(a)) ] 

for i in range(1,len(a)): 
    for j in range(1,len(a[0])): 
    if a[i-1][j-1] <= a[i][j-1] <= a[i][j] and a[i-1][j-1] <= a[i-1][j] <= a[i][j]: 
     m[i][j] = min(m[i-1][j],m[i][j-1],m[i-1][j-1]) + 1 

for i in m: 
    print i 

""" 
[1, 1, 1, 1, 1, 1] 
[1, 1, 2, 1, 1, 1] 
[1, 2, 2, 1, 1, 1] 
[1, 2, 3, 1, 1, 2] 
[1, 2, 3, 1, 1, 1] 
""" 

Answer 2

的问题是你的算法是错误的;你需要一个完全不同的。

你的算法计算是通过矩阵的最长增长路径的长度，即8：

   , , , , , 0 
       , , , 6, 2, 1 
       , , 20, 10, , 
       , , 23, , , 
       , , 24, , , 

它通过计算，每个元素在基体中，最长的增加路径的长度其结束于该元件：

   2, 1, 2, 1, 4, 1 
      1, 2, 5, 4, 3, 2 
      2, 3, 6, 5, 1, 3 
      3, 4, 7, 1, 2, 4 
      4, 5, 8, 2, 1, 2 

，然后选择最大的这样的长度（即8）。

相反，你需要做的是计算，对于矩阵中的每个元素，最大的大小排序有该元素在其右下角方块子矩阵：

   1, 1, 1, 1, 1, 1 
      1, 1, 2, 1, 1, 1 
      1, 2, 2, 1, 1, 1 
      1, 2, 3, 1, 1, 2 
      1, 2, 3, 1, 1, 1 

，然后选择最这样的大小（即3）。需要注意的是，与最长增加路径问题不同，这不需要递归和记忆;相反，这是一个纯粹的动态编程问题。您可以从矩阵的顶部到底部工作，从左到右依靠计算每个子结果，仅取决于您已计算的子结果。 （我注意到你用[dynamic-programming]标记了这个问题，所以我认为这就是你的教授希望你做的事情。）