最长递增序列2D矩阵递归
我被提出了一项新的家庭作业，至少可以说有点令人沮丧。 基本上，我创建了一个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的值是否严格更大，而且还必须考虑对角线。 我已经做过广泛的研究，如何递归地解决这个问题，但我运气不好，递归是我最弱的主题（是的，我知道它在某些情况下有多强大）。 我见过类似的post，有人提到了丙烯酸图，但那不是我想要的。
到目前为止，我基本上用0填充了我的2D数组，因此我不必担心边界，我使用嵌套for循环来遍历2D数组。 在这些循环中，我基本上检查N，NE，E，SE，S，SW，W，NW是否具有比当前元素更大的值。 对不起，如果我对你们中的一些人感到不安，这是我第一次尝试发帖。 如果你需要我发布一些代码，我会这样做。 非常感谢您的宝贵时间！
更新
我最近学习了动态编程，我找到了一个更好的算法。
算法很简单：找到每个点的最长长度，并将结果记录在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个周围点。
certificate
如果路径不以局部最小值开始，则起点必须大于至少一个周围点，因此可以扩展路径。 拒绝！ 因此，路径必须以局部最小值开始。 类似的原因以局部最大值结束。
伪代码
对于所有当地的最低
做一个recursive_search
recursive_search（点）
如果点是局部最大值
结束，比较（并在必要时替换）最长
其他
对于所有更大的周边点
做一个recursive_search
另一种方法：按矩阵条目中的值对矩阵条目进行排序。 从最大到最小的迭代。 对于每个条目，计算恒定时间内的最长路径：对于较大的邻居（已经计算过），最长路径是最长路径的1 +最大值。
总时间：O（mn log（mn））对矩阵条目进行排序，加上O（mn）以查找最长路径。
java完整的解决方案它将pathes返回到控制台，并返回最长的序列，但你可以很少修改这段代码，你也将获得最长的路径
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; } } }
我知道这是一个非常古老的问题，但是，我正在阅读Lubomir Stanchev的书“通过游戏学习Java”，第14章项目是精确的2D整数数组。 分配是找到最长的增加序列，但只能在两个方向，南方和东方，没有对角线或任何东西。 我花了几个小时才弄清楚逻辑，也不习惯递归。 我通过创建辅助方法来简化问题，该方法检查下一个索引在该方向上是否有效（即，不超出范围且大于当前值）。 然后我将基本案例放在方法的开头，即没有下一个可能的索引时。 棘手的部分是String变量的赋值，因此每次方法使用递归时索引都保存在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; }
}