(UVA) Cutting Sticks - Solution

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

The solution below used Dynamic Programming to solve this problem.


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

class Main {
    public int lengthStick;
    public int numCuts;
    public int[] cuts;
    public int[][] memo;
   
    public int rec(int start, int end) {
        if (memo[start][end] != -1) {
            return memo[start][end];
        }

        int numPossible = 0;
        for (int i = 0; i < numCuts; i++) {
            if (cuts[i] > start && cuts[i] < end) {
                numPossible++;
            }
        }
        if (numPossible == 0) {
            return 0;
        }
       
       
        int price = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < numCuts; i++) {
            if (cuts[i] <= start || cuts[i] >= end) {
                continue;
            }
            price = (end-start) + rec(start, cuts[i]) + rec(cuts[i], end);
            minPrice = Math.min(minPrice, price);
        }
       
        memo[start][end] = minPrice;
        return memo[start][end];
    }
    
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        lengthStick = Integer.parseInt(br.readLine());
        while (lengthStick != 0) {
            numCuts = Integer.parseInt(br.readLine());
            cuts = new int[numCuts];
            String line = br.readLine();
            String[] s = line.split(" ");
            for (int i = 0; i < numCuts; i++) {
                cuts[i] = Integer.parseInt(s[i]);
            }
           
            memo = new int[lengthStick+1][lengthStick+1];
            for (int i = 0; i < lengthStick+1; i++) {
                for (int j = 0; j < lengthStick+1; j++) {
                    memo[i][j] = -1;
                }  
            }
           
            bw.write("The minimum cutting is " + rec(0, lengthStick) + ".\n");
            lengthStick = Integer.parseInt(br.readLine());
        }
                                                      
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}