2. Number tower

点击查看考点

多维数组, 递归函数

Number tower

The image above illustrates an number tower.

You need to move from top to the bottom, and each time you have to choose only one path and add the number altogether, of which the largest number is called the length of this number tower.

Write an program to create a number tower and find out its length.

Tips: You can use recursion to calculate from the bottom, length function, which caculate the maximum of length of the lower left number and lower right, and recurs to the upper floor.

翻译

上面的图片表示了一个数塔.

你需要从上往下移动, 每次都只选择一条路径并加上所对应的数字. 这样所得到的最大数字即为数塔的长度.

编写一个程序创造这个数塔并输出其长度.

提示: 你可以使用递归从底部计算长度. 先得到更底层左边数字和右边数字的最大值, 据此递归至更上层.

点击查看参考解答

[在线代码 o4zPWE3Pf]

将数塔存储为二维数组:

9  0  0  0  0
12 15 0  0  0
10 6  8  0  0
2  18 9  5  0
19 7  10 4  16

自底向上看, 注意到对于 (i, j) 处的数, 它与 (i - 1, j - 1) 和 (i - 1, j) 连接, 构成两条路径. (i, j) 对应的最大路径值为:

(i, j) 值 + max{(i - 1, j - 1) 构成的最大路径, (i - 1, j) 构成的最大路径}