数字三角形

如图，该三角形每一行有一个非负数字，除了最后一行外，每个数字的左下方和右下方各有一个数字。从第一行开始，每次可以向左下或者右下走一格，直至走到最后一行。把沿途经过的数字加起来，得到的最大值是多少？
这个三角形看起来形似杨辉三角，也有些像一棵树，其实这是一个标准的有向无环图。从第一行到最后一行，可以分成n个步骤，而每个步骤有两种选择（第一层除外），那么一共有2^(n-1)条路径。如果采用递归枚举算法，复杂度是指数级别。

高效的算法是动态规划，这种算法常用于图论问题中求最优解，其核心是状态和状态转移方程。
首先定义状态，假设 d( i , j )表示从第 i 行第 j 个数字到低底层的最佳路径之和，那么有d( i , j ) = a( i , j ) + max { d( i + 1, j ) , d( i + 1, j +1 ) } ，这就是状态转移方程，方程的特点是全局最优解包含局部最优解。

int dp(int i, int j) {
    if (i >= a.length) {
        return 0;
    }
    return a[i][j] + Math.max(dp(i + 1, j), dp(i + 1, j + 1));
}

这里存在重复计算的问题，因为动态规划中存在着重复子问题（想想为什么树中不会存在）。怎样消除重复计算呢？记忆化搜索，或者递推。

private int[][] a;
private int[][] b; // 里面的元素初始值是-1

int dp(int i, int j) {
    if (i >= a.length) {
        return 0;
    }
    if (b[i][j] >= 0) {
        return b[i][j];
    } 
    return b[i][j] = a[i][j] + Math.max(dp(i + 1, j), dp(i + 1, j + 1));
}

记忆化搜索需要辅助空间来记录中间的计算结果，下面写一个递推版本。

int recurrence() {
    int len = a.length;
    int[][] d = new int[len][len];
    d[len - 1] = a[len - 1].clone();
    for (int i = len - 2; i >= 0; i--) {
        for (int j = 0; j < i + 1; j++) {
            d[i][j] = a[i][j] + Math.max(d[i + 1][j], d[i + 1][j + 1]);
        }
    }
    // 打印计算结果
    for (int[] ints : d) {
        System.out.println(Arrays.toString(ints));
    }
    return d[0][0];
}

递归的关键是边界和计算顺序，时间复杂度是 状态总数 * 每个状态的决策树 * 决策时间，在本题中是O(n^2)。
最后给出测试代码：

public class NumberTriangle {

    public NumberTriangle(int[][] a) {
        this.a = a;
        b = new int[a.length][a.length];
        for (int[] ints : b) {
            Arrays.fill(ints, -1);
        }
    }

    private int[][] a;
    private int[][] b;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.out.print("line " + i + ": ");
            String input = scanner.nextLine();
            List<Integer> list = Stream.of(input.split("\\s+")).map(Integer::parseInt).collect(Collectors.toList());
            for (int j = 0; j < i + 1; j++) {
                a[i][j] = list.get(j);
            }
        }
        NumberTriangle triangle = new NumberTriangle(a);
        System.out.println(triangle.dp(0, 0));
    }
}

数字三角形

推荐阅读更多精彩内容