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.}