Problem 18: Maximum path sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

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

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method!


Solution:
This problem can be solved by brute force, but then there's a similar problem,Problem so large that it would take years to solve that by brute force even if you have a very fast machine! By brute force the solution is simple , all you have to do is check each path, and then  find the one with maximum sum.

but since we would need to reuse the code in a later problem, I tried this using dynamic programming. I stored the triangle in an array, I read it from a file, Since a similar problem is again presented later, which is way much larger then this one, writing the array manually was not feasible. 

here's the function that reads the file and stores the triangle in a double dimensional array:

public static int[][] FileRead( String Filepath)throws IOException
 {   int Triangle[][] = {{0},{0}};
  try {
   
   FileReader fr = new FileReader(Filepath);
   FileReader fr2 = new FileReader(Filepath);
   BufferedReader br = new BufferedReader(fr);
   BufferedReader br2 = new BufferedReader(fr2);
   
   String S ;
   String Sline[];
   int lines =0;
   
   while((S=br.readLine())!=null)
   {
    
   lines++; 
   
   }
   
   Triangle = new int[lines][lines];
   Sline = new String[lines];
   
   int j= 0;
   
   while ((S=br2.readLine())!=null) 
   { 
    
    Sline = S.split(" ");
   for(int i = 0; i< sline .length=".length" i="i" integer.parseint="integer.parseint" j="j" line="line" pre="pre" triangle="triangle">

This function takes the file path as parameter and returns an integer array with the values of the triangle.

the triangle is stored in the following format:
3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

now by dynamic programming we have divide the solutions into smaller solutions, that is we divide the triangle into multiple triangles in a similar way :

we keep doing this untill we reach a minimal problem.

the java code to do this given below:

 

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;


public class Prob18 {

 /**
  * @param args
  */
 public static void main(String[] args) throws IOException
 {
 
  String s= "filepath";
  int Triangle[][] = FileRead(s);
  //System.out.println(Triangle.length);
  int lines = Triangle.length;
 

  for (int i = lines - 2; i >= 0; i--) {
      for (int j = 0; j <= i; j++) {
          Triangle[i][j] += Math.max(Triangle[i+1][j],Triangle[i+1][j+1]);
      }
  }

System.out.println(Triangle[0][0]);
 
 } 
 
 
 public static int[][] FileRead( String Filepath)throws IOException
 {   int Triangle[][] = {{0},{0}};
  try {
   
   FileReader fr = new FileReader(Filepath);
   FileReader fr2 = new FileReader(Filepath);
   BufferedReader br = new BufferedReader(fr);
   BufferedReader br2 = new BufferedReader(fr2);
   
   String S ;
   String Sline[];
   int lines =0;
   
   while((S=br.readLine())!=null)
   {
    
   lines++; 
   
   }
   
   Triangle = new int[lines][lines];
   Sline = new String[lines];
   
   int j= 0;
   
   while ((S=br2.readLine())!=null) 
   { 
    
    Sline = S.split(" ");
   for(int i = 0; i< Sline.length;i++)
   {
    Triangle[j][i] = Integer.parseInt(Sline[i]);
   }
   j++;
   }
   
  
  
   
  fr.close(); 
  } catch (FileNotFoundException e) {
   // TODO Auto-generated catch block
   System.out.println("Error reading file");
  }
  
 return Triangle;
 }

}

"filepath" should be the path of your text file which stores the triangle.

If you have any confusions, comment , I'd be obliged to clear them.