我正在尝试计算数组中三角形的总和,其中将其下面的三个数字的最大值相加(直接在下面、下面和左边一个、下面和右边一个)。我相信我的问题在于我在哪里/如何获取每个三角形中的行数 (numRows),因为它永远不会更新超过 3。我不确定我应该采取什么不同的方法来更新它,因为我认为每当调用递归方法并每次递增 1 时它都应该更新,但显然情况并非如此。下面是我的代码。提前谢谢大家!
/**
*
* @author Ra'kiir
*/
public class RecursiveTriangleSum {
public static int globalRows = 0;
/**
* @param args the command line arguments
* @throws java.io.FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException {
int[][] tempArray = new int[][]{
{4}, //number of test cases
{3}, //start: test case 1
{1},
{1, 2},
{1, 2, 3},
{5}, //start: test case 2
{1},
{1, 3},
{3, 2, 1},
{2, 1, 3, 4},
{3, 5, 2, 4, 1},
{1}, //start: test case 3
{3},
{6}, //start: test case 4
{1},
{2, 1},
{1, 2, 3},
{4, 3, 2, 1},
{1, 2, 3, 4, 5},
{3, 4, 5, 1, 2, 3}
};
int numTestCases = tempArray[0][0];
globalRows++;
for (int z=0; z<numTestCases; z++) {
int sum = recursiveTriSum(tempArray, globalRows, 0);
System.out.println("The Sum is: " + sum);
}
} //End main method
public static int recursiveTriSum(int[][] array, int i, int j) { //i=row, j=column
// System.out.println("Recursion Runs");
int numRows = array[globalRows][0];
if (i>numRows) {
// System.out.println("IF");
return 0;
}
else {
// System.out.println("Else");
int t1 = recursiveTriSum(array, i+1, j);
int t2 = recursiveTriSum(array, i+1, j+1);
int t3 = recursiveTriSum(array, i+1, j-1);
int p1 = Math.max(t1, t2);
int p2 = array[i][j] + Math.max(p1, t3);
globalRows++;
numRows--;
return p2;
}
} //End recursiveTriSum method
} //End of Main Class
最佳答案
迭代每个三角形:
- 获取三角形的第一行,初始化变量说 sum = 第一个元素,另一个变量说索引 = 0。
- 移动到三角形中的下一行,从索引开始并选取接下来的两个元素。如果第一个元素大于第二个,则不要增加变量,即索引,否则增加它并将较大的值添加到总和中。
例如
If(array[index] > array[index+1]) sum += array[index]; else{ sum += array[index+1]; index++; }依此类推,直到三角形的最后一行。
关于Java - 三角形的递归和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28785948/