package com.yao.Algorithms; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.Reader; /** * * @author shuimuqinghua77 @date 2011-12-4 * */ public class Problem18 { private final static int SIZE = 100; public static void main(String[] args) throws Exception { /*** * 打开文件triangle.txt 内容如下 * 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 */ File file = new File("C:\\Users\\Administrator\\Desktop\\triangle.txt"); Reader in = new FileReader(file); BufferedReader br = new BufferedReader(in); /*** * 把文件里面的内容读到数组arr中 */ int[][] arr = new int[SIZE][SIZE]; int lineNum = 0; do { String line = br.readLine(); if (line == null) break; line = line.trim(); String[] str = line.split(" "); for (int j = 0; j < str.length; j++) { arr[lineNum][j] = Integer.parseInt(str[j]); } lineNum++; } while (true); br.close(); in.close(); /** * 动态规划 * 问题Problem18转化求点S(顶点)到 点F(最底端的SIZE个节点)的最大距离中的最大值, * 点A到点B的最大距离,就是点A到点B的父节点(B点有2个父节点)的最大距离+父节点到B的距离。题目转化为层层推进,即一层一层求解 */ int[] premax = new int[SIZE];/**依次存放每一层中的点到顶点的最大值*/ for (int k = 0; k < SIZE; k++) { int[] max = new int[SIZE]; for (int m = 0; m <= k; m++) { if (m == 0) max[m] = arr[k][m] + premax[m]; else { max[m] = premax[m] > premax[m - 1] ? arr[k][m] + premax[m] : arr[k][m] + premax[m - 1]; } } premax = max; } int result = 0; for (int mm : premax) { if (mm > result) result = mm; } System.out.println(result); } }