(UVA) The Twin Towers - Solution

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

The solution below used the concept of Longest Common Subsequence (LCS), related to Dynamic Programming, to solve this problem.


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

class Main {
    public int numTilesN1;
    public int numTilesN2;
    public int[] tilesN1;
    public int[] tilesN2;
    public int[][] memo;
  
    public int rec(int indexN1, int indexN2) {
        if (indexN1 == numTilesN1 || indexN2 == numTilesN2) {
            return 0;
        }
      
        if (memo[indexN1][indexN2] != -1) {
            return memo[indexN1][indexN2];
        }
      
        int jumpLeft = rec(indexN1+1, indexN2);
        int jumpRight = rec(indexN1, indexN2+1);
        int equal = (tilesN1[indexN1] == tilesN2[indexN2]) ? rec(indexN1+1, indexN2+1) + 1 : rec(indexN1+1, indexN2+1) + 0;
      
        memo[indexN1][indexN2] = Math.max(jumpLeft, Math.max(jumpRight, equal));
        return memo[indexN1][indexN2];
    }
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numCase = 0;
        numTilesN1 = sc.nextInt();
        numTilesN2 = sc.nextInt();
        memo = new int[101][101];
        while (numTilesN1 != 0 || numTilesN2 != 0) {
            tilesN1 = new int[numTilesN1];
            for (int i = 0; i < numTilesN1; i++) {
                tilesN1[i] = sc.nextInt();
            }
          
            tilesN2 = new int[numTilesN2];
            for (int i = 0; i < numTilesN2; i++) {
                tilesN2[i] = sc.nextInt();
            }
          
            for (int i = 0; i < numTilesN1; i++) {
                for (int j = 0; j < numTilesN2; j++) {
                    memo[i][j] = -1;
                }
            }
          
            bw.write("Twin Towers #" + ++numCase + "\n");
            bw.write("Number of Tiles : " + rec(0, 0) +"\n\n");
          
            numTilesN1 = sc.nextInt();
            numTilesN2 = sc.nextInt();
        }
                                             
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}