java - 使用动态规划查找最大大小的已排序子矩阵

Question

我正在尝试解决一个动态规划问题，包括有一个矩阵，找到最大尺寸的排序子矩阵。

我想用动态规划求解，但我没有得到正确的结果。

我的程序由两种方法组成:第一种方法递归地检查靠近参数给定位置的元素。然后，在第二种方法中，我调用了前一种方法来查找子矩阵的最大阶数，但它没有返回正确的结果。

例如，对于这个矩阵，用 new Solution(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

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

您的算法计算的是通过矩阵的最长递增路径的长度，即 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] 标记了这个问题，所以我假设这是你的教授希望你做的。)