三角形最大路径

看到公司一个前端面试题，题目如下：
一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。
5
8 4
3 6 9
7 2 9 5
例子中的最优方案是：5 + 8 + 6 + 9 = 28
这是一道很典型的DFS+动态规划的问题，所以用数组构造这个三角形无疑是最直接的方式。
代码如下：

public class LongestPathInTriangle {

    private int height;
    private int[][] triangle;
    private int[][] path;
    public int maxRoute = 0;

    public LongestPathInTriangle(int[][] triangle) {
        this.triangle = triangle;
        this.height = triangle.length;
        this.path = new int[height][height];
        path[0][0] = triangle[0][0];
    }

    public void dfs(int x, int y) {
        if (x == height - 1) {
            return;
        }
        int root = path[x][y];
        int left = triangle[x + 1][y];
        int right = triangle[x + 1][y + 1];
        path[x + 1][y] = Math.max(path[x + 1][y], root + left);
        path[x + 1][y + 1] = Math.max(path[x + 1][y + 1], root + right);
        maxRoute = Math.max(path[x + 1][y], path[x + 1][y + 1]);
        for (int i = 0; i <= y + 1; i++) {
            dfs(x + 1, i);
        }
    }

    public static void main(String[] args) {
        int[][] triangle = {
                {5, 0, 0, 0},
                {8, 4, 0, 0},
                {4, 2, 1, 0},
                {7, 2, 9, 50}
        };        
        LongestPathInTriangle test = new LongestPathInTriangle(triangle);
        test.dfs(0, 0);
        System.out.println(test.maxRoute);
    }