java 最长递增序列 2D 矩阵递归
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6558710/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Longest Increasing Sequence 2D matrix recursion
提问by Mike73
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
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.
所以，我不仅要检查 N、S、E、W 是否严格大于值，而且我还必须考虑对角线。我已经对如何递归解决这个问题进行了广泛的研究，但是我运气不佳，递归是我最弱的主题（是的，我知道它在某些情况下有多么强大）。我看过类似的帖子，有人提到了亚克力图，但这不是我要找的。
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!
到目前为止，我基本上用 0 填充了我的 2D 数组，这样我就不必担心边界，并且我正在使用嵌套的 for 循环来遍历 2D 数组。在这些循环中，我基本上是在检查 N、NE、E、SE、S、SW、W、NW 是否具有比当前元素更大的值。对不起，如果我让你们中的一些人感到不安，这是我第一次尝试发帖。如果你需要我发布一些代码，我会这样做。非常感谢您的宝贵时间！
回答by Dante May Code
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];
}
Recursion
递归
1) start with a point (and this step has to be taken for all necessary points)
1）从一个点开始（所有必要的点都必须执行此步骤）
2) ifno surrounding point is greater, then this path ends; elsepick a greater surrounding point to continue the path, and go to 2).
2）如果周围没有更大的点，那么这条路径结束；否则选择一个更大的周围点继续路径，然后转到2）。
2.1) if the (ended) path is longer than recorded longest path, substitute itself as the longest.
2.1）如果（结束）路径比记录的最长路径长，则将其自身替换为最长路径。
Hint
暗示
(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.
对于最长路径，起点为局部极小点，终点为局部极大点。
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.
局部最大值，大于（或等于）所有（最多）8 个周围的点。
Proof
证明
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.
如果路径不是以局部最小值开始，则起点必须至少大于周围的点，因此可以扩展路径。拒绝！因此，路径必须以局部最小值开始。类似的原因以局部最大值结束。
pseudo code
伪代码
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
回答by Irit Katriel
Another approach: Sort the matrix entries by the value in them. Iterate from the largest to the smallest. For each entry, compute the longest path in constant time: longest path is 1 + maximum over longest paths for larger neighbors (which have already been computed).
另一种方法：按其中的值对矩阵条目进行排序。从最大到最小迭代。对于每个条目，计算恒定时间内的最长路径：最长路径是 1 + 较大邻居（已计算）的最长路径的最大值。
Total time: O(mn log(mn)) to sort the matrix entries, plus O(mn) to find the longest paths.
总时间：O(mn log(mn)) 对矩阵条目进行排序，加上 O(mn) 以找到最长路径。
回答by Eugene Kisly
java complete solutionIt returns pathes to console, and returns longest sequence, but you can little modify this code, and you'll get longest path also
java完整的解决方案它返回路径到控制台，并返回最长的序列，但是你几乎不能修改这段代码，你也会得到最长的路径
public class HedgehogProblemSolver {
private int rowCount;
private int columnCount;
private int[][] fieldArray;
private int maxApplesCount = 0;
public HedgehogProblemSolver(int inputArray[][]) {
this.fieldArray = inputArray;
rowCount = inputArray.length;
columnCount = inputArray[0].length;
}
public int solveProblem() {
findPathRecursive(0, 0, "", 0);
System.out.println("Max apple count: " + maxApplesCount);
return maxApplesCount;
}
private void findPathRecursive(int row, int column, String path, int applesCount) {
if (row == rowCount - 1) {
//last row
for (int i = column; i < columnCount; i++) {
//just go right until last column
path += "-[" + fieldArray[row][i] + "](" + row + ", " + i + ")";
applesCount += fieldArray[row][i];
}
pathResult(path, applesCount);
return;
}
if (column == columnCount - 1) {
//last column
for (int i = row; i <= rowCount - 1; i++) {
//just go down until last row
path += "-[" + fieldArray[i][column] + "](" + i + ", " + column + ")";
applesCount += fieldArray[i][column];
}
pathResult(path, applesCount);
return;
}
path = path + "-[" + fieldArray[row][column] + "](" + row + ", " + column + ")";
applesCount += fieldArray[row][column];
//go down
findPathRecursive(row + 1, column, path, applesCount);
//go right
findPathRecursive(row, column + 1, path, applesCount);
}
private void pathResult(String path, int applesCount) {
System.out.println("Path: " + path + "; apples: " + applesCount);
if (applesCount > maxApplesCount) {
maxApplesCount = applesCount;
}
}
}
回答by Ricardo Ferreira Pe?alver
I know this is a very old question, but, I'm reading Lubomir Stanchev's book titled Learning Java Through Games, and the Chapter 14 Project is that exact 2D array of integers. The assignment is to find the longest increasing sequence but only in two directions, South and East, no diagonals or anything. Still it took me hours to figure out the logic, not used to the recursion either. I simplified the problem by creating auxiliary methods that check if the next index is valid in that direction (that is, not out of bounds and greater than the current value). Then I placed the base case at the start of the method, which is when there is no next possible index. The tricky part is the assignment of the String variable, so each time the method uses recursion the indexes are saved in the String. I solved it by using the String.length() method to compare the length of each sequence, when there is more than one possible path. With the basic logic in place, in order to expand the method all that it would require is creating more auxiliary methods in the direction needed, and adding those directions to the logic.
我知道这是一个非常古老的问题，但是，我正在阅读 Lubomir Stanchev 的书《通过游戏学习 Java》，第 14 章项目就是那个精确的二维整数数组。任务是找到最长的递增序列，但只在两个方向，南和东，没有对角线或任何东西。我仍然花了几个小时来弄清楚逻辑，也不习惯递归。我通过创建辅助方法来简化问题，这些方法检查下一个索引在该方向是否有效（即，未超出范围且大于当前值）。然后我将基本情况放在方法的开头，也就是没有下一个可能的索引时。棘手的部分是 String 变量的分配，因此每次该方法使用递归时，索引都保存在 String 中。我通过使用字符串解决了它。length() 方法来比较每个序列的长度，当存在多个可能的路径时。基本逻辑到位后，为了扩展方法，它所需要的只是在所需方向上创建更多辅助方法，并将这些方向添加到逻辑中。
public static boolean isRightLegal(int[][] array, int row, int column) {
//if we are at the last column
if (column >= array[row].length - 1) {
return false;
}
//if we are not at the one before last
if ((column + 1) < array[row].length) {
//if the current number is greater than the next
if (array[row][column] > array[row][column + 1]) {
return false;
}
}
return true;
}
public static boolean isDownLegal(int[][] array, int row, int column) {
//if we are at the last row
if (row >= array.length - 1) {
return false;
}
//if we are not at the one before last
if ((row + 1) < array.length) {
//if the current number is greater than the next
if (array[row][column] > array[row + 1][column]) {
return false;
}
}
return true;
}
public static String recursiveSequence(int[][] array, int row, int column, String path) {
//base case: when we reach the end of the sequence
if (! isDownLegal(array, row, column) && ! isRightLegal(array, row, column)) {
return "(" + row + "," + column + ") ";
}
path = "(" + row + "," + column + ") ";
//if both paths are valid
if (isDownLegal(array, row, column) && isRightLegal(array, row, column)) {
//calculate each sequence and pick the longest one
if (recursiveSequence(array, (row + 1), column, path).length() > recursiveSequence(array, row, (column + 1), path).length()) {
path += recursiveSequence(array, (row + 1), column, path);
} else {
path += recursiveSequence(array, row, (column + 1), path);
}
return path;
}
//if only the down path is valid
if (isDownLegal(array, row, column)) {
path += recursiveSequence(array, (row + 1), column, path);
}
//if only the right path is valid
if (isRightLegal(array, row, column)) {
path += recursiveSequence(array, row, (column + 1), path);
}
return path;
}
}
}
