文件名称：数字三角 dp
文件大小：810B
文件格式：CPP
更新时间：2014-12-04 14:37:59
数字三角 dp
问题描述：给定一个由n行数字组成的数字三角形，如下图所示。试用动态规划算法，计算出从三角顶部至底部的一条路径，使得该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式 第一行是数字三角的行数n，1<=n<=100。接下来n行是数字三角各行中的数字，所有数字在0~99之间。 输出格式 输出两行，第一行是计算出的最大路径的和值，第二行是该路径上的数字。若有多条路径，靠右的路径优先（即仅仅输出靠右的路径即可，无需多条路径都输出）。 如： Input: 5 7 3 8 8 1 6 2 7 4 4 4 5 2 4 5 有两条路径：7-3-8-7-5和7-8-6-4-5都为30，由于后者靠右，因此仅输出后者。 Output: 30 7 8 6 4 5 输入样例 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出样例 30 7 3 8 7 5