I am trying to understand dp with bitmasks now, I got most of the trick but I don’t yet understand the nitty gritty of the state transition. There is excellent explanation in this thread The example is ASSIGN problem from spoj. I do understand how the recurrence is derived f(n, s) must be the sum of all f(n-1, s) where e(Assigned to nth student) should not be a part of the combination. However, what I do not get is, the final dp state, i.e
dp[i] = dp[i] + dp[i & ~(1 << k)];
I understand the second operand in RHS, it is the assignment except the ‘e’ in s. The first operand got me real confused. Why is it being added? How is it calculated before? Can anybody give me the statement of this relation term by term in an English Sentence so that I can read what exactly this recurrence should sound like? The implementation of the above recurrence is in this thread Much thanks!