(UVA) Marks Distribution - Solution

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

The solution below used Dynamic Programming to solve this problem.


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

class Main {
    public int numSubjects;
    public int minMark;
    public int[][] matrix;
   
    public int rec(int grade, int subjectID) {
        if (grade < minMark) {
            return 0; // invalid
        }
       
        if (subjectID == numSubjects) {
            return 1; // plus one way
        }
       
        if (matrix[grade][subjectID] != -1) {
            return matrix[grade][subjectID];
        }
       
        int numOp = 0;
        for (int i = minMark; i < grade; i++) {
            numOp += rec(grade-i, subjectID+1);
        }
       
        matrix[grade][subjectID] = numOp;
        return matrix[grade][subjectID];
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = sc.nextInt();
        for (int test = 0; test < numTests; test++) {
            numSubjects = sc.nextInt();
            int totalMark = sc.nextInt();
            minMark = sc.nextInt();
           
            matrix = new int[totalMark+1][numSubjects+1];
            for (int i = 0; i < totalMark+1; i++) {
                for (int j = 0; j < numSubjects+1; j++) {
                    matrix[i][j] = -1;
                }
            }
           
            bw.write(rec(totalMark, 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);
    }
}