アットコーダ、edpc-o問題

Question

問題
https://atcoder.jp/contests/dp/tasks/dp_o

いろんな解説を拝見して、
「男性をiまで検討した時の、マッチング済の女性の集合S」をdp[i][S]とするということ、
Sを2進数として見て、1の本数を数えればiと一致するので、結局dp[S]ということ
はわかりました。

dpを書くときのdp[S]とdp[S-1]の関係性を記述する方法がわかりません。

どなたかご教示ください。