java--study||O.o--记忆化搜索DFS

参考代码:

import java.util.Scanner;
 
public class Main
{   public static void main(String[] args)
    {   Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        arr = new int[n][n];
        for(int i = 0; i < n; i++)
            for(int j  = 0; j <= i; j++)
                arr[i][j] = scanner.nextInt();
        scanner.close();
        memory = new int[n][n];//记录当前位置的最大值
        System.out.print(dfs(0, 0));
    }
    static int n, arr[][], memory[][];
    static int dfs(int x, int y)
    {   if(memory[x][y] > 0)
            return memory[x][y];
        if(x == n - 1)
            return memory[x][y] = arr[x][y];
        int l1 = dfs(x + 1, y);
        int l2 = dfs(x + 1, y + 1);
        memory[x][y] = Math.max(l1, l2) + arr[x][y];
        return memory[x][y];
    }
}