(UVA) Bar Codes - Solution

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

The solution below used Dynamic Programming to solve this problem.


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

class Main {
    public int numUnits;
    public int numBars;
    public int numMaxSequence; // units wide
    public long[][][] matrix;
   
    public long rec(int pos, int totalBars, int sizeSeq) {
        if (totalBars > numBars) {
            return 0;
        }
        if (sizeSeq > numMaxSequence) {
            return 0;
        }
       
        if (pos == numUnits) {
            if (totalBars == numBars) {
                return 1;
            }
            return 0;
        }
       
        if (matrix[pos][totalBars][sizeSeq] != -1) {
            return matrix[pos][totalBars][sizeSeq];
        }
       
        long numOp = 0;
        numOp += rec(pos+1, totalBars, sizeSeq+1);
        numOp += rec(pos+1, totalBars+1, 1);
       
        matrix[pos][totalBars][sizeSeq] = numOp;
        return matrix[pos][totalBars][sizeSeq];
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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