最长递增序列二维矩阵递归 [英] Longest Increasing Sequence 2D matrix recursion

问题描述

我一直psented一个新的家庭作业已经有点令人沮丧的，至少可以说$ P $。基本上，我有一个创建整数的二维数组如下：

I have been presented with a new homework assignment that has been somewhat frustrating to say the least. Basically, I have a create a 2D array of integers as follows:

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

和我写一个递归方法，或函数随你便，计算最长递增子序列。在本例中，最长的增加子序列如下：

and I am to write a recursive method, or function as you will, to calculate the longest increasing sub sequence. In this example, the longest increasing sub sequence is the following:

(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的值严格大于，但我也必须考虑对角线。我已经做了广泛的研究，在如何解决这个递归，但是我还没有多少运气和递归是我最弱的科目（是的，我知道如何强大，它可以在某些情况下）。我见过类似的东西贴出来，如果​​有人提到丙烯酸图表，但是这不是我所期待的。

So, not only am I to check N,S,E,W for values strictly greater, but I also have to account for diagonals. I have done extensive research in how to solve this recursively however I haven't had much luck, and recursion is my weakest subject (yes I know how powerful it can be in certain situations). I have seen something similar posted, where someone mentioned an acrylic graph, but that's not what I am looking for.

到目前为止，我已经基本上填补我的二维数组0的，这样我就不必担心边界，而我使用嵌套的for循环遍历二维数组。在这些循环我基本上检查，如果N，NE，E，SE，S，SW，W，NW比当前元素更大的价值。很抱歉，如果我不高兴你们中的一些，这是我在后的第一次尝试。如果你需要我来发布一些code，我将这样做。非常感谢您的时间！

So far, I've basically padded my 2D array with 0's so that I don't have to worry about bounding, and I am using nested for loops to traverse the 2D array. Within those loops I am basically checking if N,NE,E,SE,S,SW,W,NW have a greater value than the current element. Sorry if I upset some of you this is my first attempt at a post. If you need me to post some code, I will do so. Thank you very much for your time!

推荐答案

我学习到的动态编程最近，我已经找到了问题的一个更好的算法。

Update

I learnt dynamic programming recently, and I have found a better algorithm for the question.

的算法是简单的：找到最长的长度为每一个点，和一个二维数组中记录结果，使我们并不需要计算最长长度为一些分再次

The algorithm is simple: find the longest length for every point, and record the result in a 2D array so that we do not need to calculate the longest length for some points again.

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）以一个点（和这个步骤，必须采取一切必要的点）

---

Recursion

1) start with a point (and this step has to be taken for all necessary points)

2）的如果的周围没有一点大，那么这条路结束; 其他的选择一个更大的周围点继续路径，并转到2）。

2) if no surrounding point is greater, then this path ends; else pick a greater surrounding point to continue the path, and go to 2).

2.1），如果（结束）路径的长度超过记录最长的路径，替换自己是最长的。

2.1) if the (ended) path is longer than recorded longest path, substitute itself as the longest.

（较少的计算，但更多的代码）

(less computation but more coding)

有关的最长路径，其中的起始点将是一个局部最小点，并且其终点将是一个极大点

For the longest path, the start point of which will be a local minimum point, and the end point of which will be a local maximum point.

本地最低，小于（或等于）所有（最多）8点周围

Local minimum, less than (or equal to) all (at most) 8 surrounding points.

本地最大，大于（或等于）所有（最多）8点周围

Local maximum, greater than (or equal to) all (at most) 8 surrounding points.

如果该路径不开始与一个局部最小值，则开始点必须大于至少一个周边点，并且因此路径可以延长。拒绝！因此，该路径必须以当地最低。类似的结束与局部最大值的原因。

If the path does not start with a local minimum, then the start point must be greater than at least a surrounding point, and thus the path can be extended. Reject! Thus, the path must start with a local minimum. Similar for the reason to end with a local maximum.

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

这篇关于最长递增序列二维矩阵递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！