(UVA) Determine it - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1461

The solution below used Dynamic Programming to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public int n;
    public int an1;
    public long[][] matrix;
   
    public long rec(int i, int j) {
        if (i == n && j == 1) {
            return an1;
        }
       
        if (matrix[i][j] != -1) {
            return matrix[i][j];
        }
       
        if (i < j) {
            long max = 0;
            for (int k = i; k < j; k++) {
                long a1 = rec(i, k);
                long a2 = rec(k+1, j);
                max = Math.max(max, (a1+a2));
            }
           
            matrix[i][j] = max;
            return matrix[i][j];
        }
        else { // i >= j
            long sum = 0;
            if (i < n) {
                long max = 0;
                for (int k = i+1; k <= n; k++) {
                    long a1 = rec(k, 1);
                    long a2 = rec(k, j);
                    max = Math.max(max, (a1+a2));
                }
                sum += max;
            }
           
            if (j > 0) {
                long max = 0;
                for (int k = 1; k < j; k++) {
                    long a1 = rec(i, k);
                    long a2 = rec(n, k);
                    max = Math.max(max, (a1+a2));
                }
                sum += max;
            }
           
            matrix[i][j] = sum;
            return matrix[i][j];
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (sc.hasNext()) {
            n = sc.nextInt();
            an1 = sc.nextInt();
           
            matrix = new long[n+1][n+1];
            for (int i = 0; i < n+1; i++) {
                for (int j = 0; j < n+1; j++) {
                    matrix[i][j] = -1;
                }
            }
           
            bw.write(rec(1, n)+"\n");
        }
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}