深度优先搜索 题解 1311: P1044 数字三角求最值

解题思路: 直接把所有路径全跑一遍，把每条路径的最终值与max进行比较，谁大谁是新max。

                好好干深度优先、广度优先遍历，好几个题目都是！图的这两个遍历，递归、非递归都给我debug跑它100遍！！！！！！

注意事项:

参考代码:

import java.util.Scanner;

/**
 * @author fzy
 * @create 2021/10/11 15:36
 **/
public class Main {
    //两个方向 左斜 右斜
    static  int[] dx={1,1};
    static  int[] dy={0,1};
    static  int max=0;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int[][] data=new int[N][N];
        for (int i=0;i<N;i++){
            for (int j=0;j<=i;j++){
                data[i][j]=sc.nextInt();
            }
        }
        dfs(data,0,0,data[0][0]);
        System.out.println(max);
    }
    public static void dfs(int[][] data,int startX,int startY,int v){
        //因为x总是要往下跑的 当x>data.length时 表示这条路径已经跑完 该回溯了
        if(startX < data.length){
            if(v > max){
                max = v;
            }
        }else{
            return;
        }
        
        for (int i = 0; i < 2; i++) {
            int nextX=startX+dx[i];
            int nextY=startY+dy[i];
            try {
                dfs(data,nextX,nextY,v+data[nextX][nextY]);
            }catch (Exception exception){
                continue;
            }
        }
    }
}