数字三角形求最大路径

/**问题描述】

    上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。 对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最 大的和。
    路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
    【输入格式】
    输入的第一行包含一个整数 N (1 < N ≤ 100)，表示三角形的行数。下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
    【输出格式】
    输出一个整数，表答案。
    【样例输入】
    5

    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

    【样例输出】
    27
    答案解析
    典型的深搜题目，再加个判断条件使得向左下走的次数与向右下走的次数相差不能超过 1，注意回溯的时候次数要减 1*/

1. 使用回溯

定义：一直向前走，直到走到头，发现这条路不是最优，那么回退一步，继续下去

将三角形拟为二叉树，那么从根节点开始，当前结点路径的最大值肯定是：当前结点值+以两个根节点为根节点的路径中较大的一个。而两个根节点的最大路径计算方式如同父节点一般。
大化小，而且每个小步骤有同样的解决方式，好像使用动态规划也可以

1.使用回溯法，首先从根节点向下深度搜索，也就是便利所有路径

2.同时，每次向下搜索，记录向左向右的步数，当到达叶子结点时，等于将所有路径都走了一遍，这时计算步数相差是否符合要求。如果不符合要求只需返回一个最小值即可。
3.然后开始向上回溯，回溯过程中，左右结点最大路径作比较，只返回较大值（过程中，不符合左右步数相差条件的会被淘汰）过程类似下面这张图（这张图只做回溯，并没有考虑第二步的步数相差条件）

	static int n;
    static int[][] triangle = new int [100][100];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n= scanner.nextInt();
        for (int i=1;i<=n;i++) {
            for(int j=1;j<=i;j++){
                triangle[i][j]=scanner.nextInt();
            }
        }
        //回溯法
        System.out.println(maxSum(1,1,0,0));
    }

    /**
    * @description 回溯法求解
    * r,j表示当前结点坐标
    * lnum，rnum表示当前结点路径左右步数
    **/
   public static int maxSum(int r,int j,int lnum,int rnum) {
       // 已经到达最底部，也就是走完了整个路径，那么判断当前左次数和右次数差是否大于1。若是大于1直接返回一个负值，表示当前路径不可用。
        if(r==n){
            if(Math.abs(lnum - rnum) <= 1){
                return triangle[r][j];
            }
            else{
                return -1;
            }
        }
        int lSum = maxSum(r+1,j,lnum+1,rnum);
        int rSum = maxSum(r+1,j+1,lnum,rnum+1);
        return (triangle[r][j] + (lSum >= rSum ? lSum : rSum));
    }

2. 使用递归

https://blog.csdn.net/m0_46226318/article/details/115188416