Here's a problem I recently came across.

Problem Summary: You are given a N * M grid, where N * M <= 40 (1 <= N, M <= 40). Initially, each square on the grid contains a spider. Then, suddenly, all spiders either move one square up, down, left, right, or stay still (and they can't move outside of the grid). If one square can contain multiple spiders, find the maximum number of spider-free grid cells after this action.

Solutions I've found online (including the official editorial) generally say something like the following:

• WLOG assume N < M. Then N <= 6.

• Let dp[n][m1][m2] = the minimum number of occupied cells in rows 0..n, such that row n can be described by the bitmask m1, and row n + 1 can be described by the bitmask m2.

• "To make a transition from D[k-1][..][..] we can iterate over all possible masks for the k-1-st column, check whether we can distribute spiders in kth column knowing the masks for k+1-st and k-1-st columns and find the minimal value of D[k-1][..][pmask] for all such masks."

I don't understand the explanation for transitions. I think that what it's saying is that for dp[n — 1][m1][m2] you can transition to dp[n][m2][..], where you loop over the state of the bitmask in row n + 1. But my questions are:

• Can someone confirm if my current understanding of the transitions is correct? Is there a better way to formulate this DP?

• How do we check if a certain pair of masks works?