UVA 11420 - Chest of Drawers

http://uva.onlinejudge.org/external/114/11420.html

You are given a chest of drawers as shown in the picture below:

Let \(N\) be defined as the total number of drawers in the wardrobe , your job is to count in how many ways you can secured exactly \(S\) drawers, a drawer is secured if the \(i\) and the \(i - 1\) are locked.

Once again we are facing a situation were a naive algorithm is going to timeout. Don't panic, Dynamic Programming to the rescue... 

The state of the DP solution is the following:

\(n\) -  current drawer

\(s\) -  count of secured drawers

\(p\) - previous drawer state (locked or unlocked)

\(rec(n, s, p)\) = total number of configurations with exactly S drawers secured

The recursion part of the solution has only two possible choices at each step, we locked the current drawer or not, depending if the previous one was locked we add one to the count of secured drawers (\(s\)) otherwise the count remain the same. 

Finally, the base case just consider the cases where the count of secured drawers is equal to \(S\).