Java - 三角形的递归和

Question

我正在尝试计算数组中三角形的总和，其中将其下面的三个数字的最大值相加(直接在下面、下面和左边一个、下面和右边一个)。我相信我的问题在于我在哪里/如何获取每个三角形中的行数 (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

Answer 1

迭代每个三角形:
- 获取三角形的第一行，初始化变量说 sum = 第一个元素，另一个变量说索引 = 0。
- 移动到三角形中的下一行，从索引开始并选取接下来的两个元素。如果第一个元素大于第二个，则不要增加变量，即索引，否则增加它并将较大的值添加到总和中。
例如

If(array[index] > array[index+1])       sum += array[index];     else{         sum += array[index+1];         index++;       }

依此类推，直到三角形的最后一行。