(UVA) Chest of Drawers - Solution

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

The solution below used Dynamic Programming to solve this problem.


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

class Main {
    public int numDrawers;
    public int numDrawersToSecure;
    public int[] drawers;
    public long[][][] state;
   
    public long rec(int currDrawer, int numLocked, int lock) {
        if (currDrawer > numDrawers || numLocked > numDrawers) {
            return 0;
        }
       
        if (currDrawer == numDrawers) {
            if (numLocked == numDrawersToSecure) {
                return 1;
            }
           
            return 0;
        }

        if (state[currDrawer][numLocked][lock] != -1) {
            return state[currDrawer][numLocked][lock];
        }
               
        long sum = 0;
        drawers[currDrawer] = 0;
        sum += rec(currDrawer+1, numLocked, 0); // keep unlocked
        drawers[currDrawer] = 1;
        int numSecureDrawers = numLocked;
        if ((currDrawer > 0 && drawers[currDrawer-1] == 1 && drawers[currDrawer] == 1) || (currDrawer == 0 && drawers[currDrawer] == 1)) {
            numSecureDrawers++;
        }
        sum += rec(currDrawer+1, numSecureDrawers, 1); // lock it
       
        state[currDrawer][numLocked][lock] = sum;
        return state[currDrawer][numLocked][lock];
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        numDrawers = sc.nextInt();
        numDrawersToSecure = sc.nextInt();
        while (numDrawers > 0 || numDrawersToSecure > 0) {
            drawers = new int[numDrawers];
            state = new long[numDrawers+1][numDrawers+1][2];
            for (int i = 0; i < numDrawers+1; i++) {
                for (int j = 0; j < numDrawers+1; j++) {
                    for (int k = 0; k < 2; k++) {
                        state[i][j][k] = -1;        
                    }      
                }
            }
            bw.write(rec(0, 0, 0)+"\n");
            numDrawers = sc.nextInt();
            numDrawersToSecure = 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);
    }
}