数字三角形算法(数字三角形递归)

 把图像看成直角三角形,当向左下走时视作——y + 1,x不动；当向右下走时视作——y + 1,x + 1。

遍历所有的条件,然后筛选出路径相加最大的值 且 左右差不超过1的 路径和。

代码抄的答案：

package lanqiaocup;


public class NumberTriangle {
    public static void main(String[] args) {
        findMaximalRoad();
    }
    
    static int max = 0;
    static int[][] triangle = {{7}, {3,8}, {8,1,0}, {2,7,4,4}, {4,5,2,6,5}};
    private static void findMaximalRoad(){
        //输出图形
        for(int i = 0; i < triangle.length; ++i){
            for(int j = 0; j <= i; ++j){
                System.out.print(triangle[i][j]);
            }
            System.out.println();
        }
        //递归查找
        dfs(0, 0, 0, 0, 0);
        System.out.print("最大值结果为：");
        System.out.println(max);
    }
    private static void dfs(int y, int x, int goLeft, int goRight, int sum){
        int len = triangle.length;
        if(y == len - 1){
            if(Math.abs(goLeft - goRight) <= 1){
                max = Math.max(max, sum + triangle[y][x]);
            }
            return;
        }
        sum += triangle[y][x];
        //向左走
        dfs(y + 1, x, goLeft + 1, goRight, sum);
        //向右走
        dfs(y +1,x + 1, goLeft, goRight +1, sum);
    }
}