最长递增序列2D矩阵递归

Question

我被提出了一项新的家庭作业,至少可以说有点令人沮丧.基本上,我有一个创建2D整数数组,如下所示:

97 47 56 36 60 31 57 54 12 55 
35 57 41 13 82 80 71 93 31 62 
89 36 98 75 91 46 95 53 37 99 
25 45 26 17 15 82 80 73 96 17 
75 22 63 96 96 36 64 31 99 86 
12 80 42 74 54 14 93 17 14 55 
14 15 20 71 34 50 22 60 32 41 
90 69 44 52 54 73 20 12 55 52 
39 33 25 31 76 45 44 84 90 52 
94 35 55 24 41 63 87 93 79 24

我将编写一个递归方法或函数,以计算最长的子序列.在此示例中,增长最长的子序列如下:

(5,0)   with value 12
(6,0)   with value 14
(6,1)   with value 15
(6,2)   with value 20
(7,2)   with value 44
(7,3)   with value 52
(7,4)   with value 54
(6,3)   with value 71
(5,3)   with value 74
(4,3)   with value 96

因此,我不仅要检查N,S,E,W的值是否严格更大,而且还必须考虑对角线.我已经做了大量的研究,如何递归地解决这个问题,但我没有太多的运气,递归是我最薄弱的主题(是的,我知道它在某些情况下有多强大).我看过类似的帖子,有人提到了丙烯酸图,但那不是我想要的.

到目前为止,我基本上用0填充我的2D数组,这样我就不必担心边界了,我使用嵌套for循环来遍历2D数组.在这些循环中,我基本上检查N,NE,E,SE,S,SW,W,NW是否具有比当前元素更大的值.对不起,如果我对你们中的一些人感到不安,这是我第一次尝试发帖.如果你需要我发布一些代码,我会这样做.非常感谢您的宝贵时间!

Answer 1

更新

我最近学习了动态编程,我找到了一个更好的算法.

算法很简单:找到每个点的最长长度,并将结果记录在2D数组中,这样我们就不需要再计算某些点的最长长度.

int original[m][n] = {...};
int longest[m][n] = {0};

int find() {
    int max = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int current = findfor(i, j);
            if (current > max) { max = current; }
        }
    }
    return max;
}

int findfor(int i, int j) {
    if (longest[i][j] == 0) {
        int max = 0;
        for (int k = -1; k <= 1; k++) {
            for (int l = -1; l <= 1; l++) {
                if (!(k == 0 && l == 0) &&
                    i + k >= 0 && i + k < m &&
                    j + l >= 0 && j + l < n &&
                    original[i + k][j + l] > original[i][j]
                   )
                    int current = findfor(i + k, j + l);
                    if (current > max) { max = current; }
                }
            }
        }
        longest[i][j] = max + 1;
    }
    return longest[i][j];
}    

递归

1)从一个点开始(必须对所有必要的点采取这一步骤)

2)如果没有更大的周围点,则该路径结束; 否则选择一个更大的周围点继续路径,然后转到2).

2.1)如果(已结束)路径长于记录的最长路径,则将其自身替换为最长路径.

暗示

(计算量少但编码多)

对于最长路径,其起点将是局部最小点,其终点将是局部最大点.

局部最小值,小于(或等于)所有(最多)8个周围点.

局部最大值,大于(或等于)所有(最多)8个周围点.

证明

如果路径不以局部最小值开始,则起点必须大于至少一个周围点,因此可以扩展路径.拒绝!因此,路径必须以局部最小值开始.类似的原因以局部最大值结束.

伪代码

for all local minimum
  do a recursive_search

recursive_search (point)
  if point is local maximum
    end, and compare (and substitute if necessary) longest
  else
    for all greater surrounding points
      do a recursive_search