小编Dil*_*ngh的帖子

最近我正在接受面试，面试官问了我一个非常有趣的问题。

我们给出了一个“N x M”的整数矩阵，我们可以跳转到严格大于同一行或列中当前数字的任何数字。我们需要找到我们可以访问的最大单元格数量是多少。我们可以从矩阵内的任意点开始。

例子 ：-

 {1, 0, 10}, 
 {3, 9, 7}, 
 {2, 6, 5}

答案：- 6

解释：- 在这种情况下，我们有多个正确的路径，其中一个路径如下所示。

0 => 1 => 2 => 3 => 7 => 10

我用 Java 编写了针对给定问题的解决方案

时间复杂度：- N * M * (N + M)

空间复杂度：- N * M

在此输入图像描述

static void longestIncreasingPath(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;

    int[][] dp = new int[n][m];
    for (int i = 0; i < n; i++)
        Arrays.fill(dp[i], -1);

    int answer = 0;
    for …