9.三角形最佳路径

【题目】
如下所示的由正整数数字构成的三角形:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

【输入】
第一行为三角形高度100≥h≥1，同时也是最底层边的数字的数目。

从第二行开始，每行为三角形相应行的数字，中间用空格分隔。

【输出】
最佳路径的长度数值。

【输入样例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【输出样例】
30

【思想】

dp，从第二行第一个开始更新当前三角形，每个数保存到达数最大的累加和，最后从最后一行找最大的即可。

【代码】

 public static int coupons(int[][] value) {
        //从第二行第一个开始更新三角形
        for (int i = 1; i < value.length; i++) {
            for (int j = 0; j <= i; j++) {
                //最左边的不能累加左上的，只能累加上方的
                if (j == 0) {
                    value[i][j] += value[i - 1][j];
                    //最右边的上面没有数，只能累加左上的
                } else if (j == i) {
                    value[i][j] += value[i - 1][j - 1];
                } else {
                    //判断上方和左上那个大，累加到当前位
                    value[i][j] = Math.max(value[i][j] + value[i - 1][j - 1], value[i][j] + value[i - 1][j]);
                }
            }
        }
        int res = 0;
        //从最后一行找最大的数返回即可
        for (int i = 0; i < value.length - 1; i++) {
            res = Math.max(res, value[value.length - 1][i]);
        }
        return res;
    }