Problem18/Problem67-白红宇

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