Triangle Problem Dynamic Programming

Triangle Problem Dynamic Programming.java

import java.util.Scanner;
import java.io.*;
/*
Se considera un triunghi de numere naturale format din n linii.

Prima linie contine un numar, a doua linie doua numere...ultima linie n numere naturale.

Cu ajutorul acestui triunghi se pot forma sume de numere naturale in felul urmator:


- se porneste cu numarul din linia 1
- succesorul unui numar se afla pe linia urmatoare plasat sub el (aceeasi coloana) sau pe diagonala (coloana creste cu 1)


CErinta:

Care este cea mai mare suma care se poate forma astfel si care sunt numerele care o alcatuiesc?

2
3 5
6 3 4
5 6 1 4

R
a b 
X Y Z
5 6 1 4

X = a[i][j] + max(5,6)

Rezultatul va fi stocat in triunghi[1][1]
S1 = 2 + 3 + 6 + 5 = 16
S2 = 2 + 5 + 4 + 1 = 12
S3 = 2 + 3 + 6 + 6 = 17
*/


public class TriangleProblem {
	

	    static final int SIZE = 101;
	    static int n;
	    static int[][] Tri = new int[SIZE][SIZE];  
	    static int[][] C = new int[SIZE][SIZE];//trebuie completat Dynamic Programming
	    static int[][] Road = new int[SIZE][SIZE];

	    public static void main(String[] args) throws IOException {

        
               //input (file-based)
               Scanner fin = new Scanner(new File("triangle.in"));

               PrintWriter fout = new PrintWriter(new FileWriter("triangle.out"));


               n = fin.nextInt();

               for(int i = 1; i <= n; ++i) {

                  for(int j = 1; j <= i; ++j) {

                        Tri[i][j] = fin.nextInt();
                  }
               }



               //print original triangle

               for(int i = 1; i <= n; ++i) {

                  for(int j = 1; j <= i; ++j) {

                        System.out.print(Tri[i][j] +" ");
                        
                  }

                  System.out.println();
               }


               //DP: intialize last row;

               for(int i = 1; i <= n ; ++i) {

                   C[n][i] = Tri[n][i]; //5 6 1 4
               }


               //DP: fill bottom-up
               for(int i = n - 1; i >= 1; i--) {

                      for(int j = 1; j <= i; j++) {

                                if(C[i+1][j] > C[i+1][j+1]) {

                                  C[i][j] = Tri[i][j] + C[i+1][j];
                                  Road[i][j] = j;

                                } else {

                                  C[i][j] = Tri[i][j] + C[i+1][j+1];
                                  Road[i][j] = j+1;

                                }
                      }     

               }

               //output maximum SUM
               fout.println(C[1][1]);

               //trace back the optimal PATH

               int i = 1, j = 1;

               while(i <= n) {
                 fout.print(Tri[i][j] + " ");
                 j = Road[i][j];
                 i++;
               }

               fin.close();
               fout.close();
	    }
}