Plates.java

public static void main(String[] args) {
    Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

    int testCases = s.nextInt();
    int caseNum = 1;
    Plates plates = new Plates();

    while (caseNum <= testCases) {
        int n = s.nextInt();
        int k = s.nextInt();
        int p = s.nextInt();

        int[][] values = new int[n][k];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                values[i][j] = s.nextInt();
            }
        }

        System.out.println(String.format("Case #%d: %d", caseNum, plates.maxPlatesBeautyValue(values, p)));
        caseNum++;
    }
}

private int maxPlatesBeautyValue(int[][] values, int numberOfPlates) {
    int n = values.length;
    int k= values[0].length;
    int p = numberOfPlates;


    // could use a one dimension array
    int[][] prefixSum = new int[n + 1][k + 1];
    int[][] lookup = new int[n + 1][p + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            prefixSum[i][j] = prefixSum[i][j - 1] + values[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= p; j++) {
            lookup[i][j] = 0;

            for (int x = 0; x <= Math.min(j, k); x++) {
                lookup[i][j] = Math.max(lookup[i][j], prefixSum[i][x] + lookup[i - 1][j - x]);
            }
        }
    }

    return lookup[n][p];
}