数字三角形问题_给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形

给定一个由n行数字组成的数字三角形，如下图所示：
        　　    19 
      　　   12  15 
      　　10   6   8 
   　　 2   18   9   5
　　 19   7   10  4  16 

　　试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（从顶部出发，在每一结点可以选择向左走或者向右走，一直走到底层）。

分析：自下而上逐层决策，逐层递推。三角形最左边一列存储在数组的第0列，三角形第一行存储在数组的第0行。

状态转移方程：res[i][j] = res[i][j]+max(res[i+1][j], res[i+1][j+1]));

代码： 

方法一：    只用一个数组

public class DigitalTriangle {
 
	public static void main(String[] args) {
 
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int n = cin.nextInt();
			int[][] tri = new int[n][n];
			for (int i = 0; i < n; i++) { // 将三角形存入数组
				for (int j = 0; j <= i; j++)
					tri[i][j] = cin.nextInt();
			}
			for (int i = n - 2; i >= 0; i--) {// 从倒数第二行开始
				for (int j = 0; j <= i; j++) {
					tri[i][j] += Math.max(tri[i + 1][j], tri[i + 1][j + 1]);
				}
			}
			System.out.println(tri[0][0]);
		}
		cin.close();
	}
}

方法二：用两个数组（一个初始输入三角形数组，一个结果存储数组） 

public class DigitalTriangle {
 
	public static void main(String[] args) {
 
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int n = cin.nextInt();
			int[][] tri = new int[n][n];// 初始数组
			int[][] res = new int[n][n]; // 结果数组
			for (int i = 0; i < n; i++) { // 将三角形存入初始数组
				for (int j = 0; j <= i; j++)
					tri[i][j] = cin.nextInt();
			}
			for (int i = 0; i < n; i++)
				res[n - 1][i] = tri[n - 1][i]; // 复制倒数第一行
			for (int i = n - 2; i >= 0; i--) {// 从倒数第二行开始
				for (int j = 0; j <= i; j++) {
					res[i][j] += (tri[i][j] + Math.max(res[i + 1][j], res[i + 1][j + 1]));
				}
			}
			System.out.println(res[0][0]);
		}
		cin.close();
	}
}

运行图：