ビットDPの思考回路について

以下のコードのアルゴリズムの思考回路がよくわかりません。

ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません（なぜDPが成立するのかがわからない）。
また、どのようにすればこのような思考でコードをかけるのでしょうか？
どなたか分かる方はいらっしゃるでしょうか？

コード元： 第16回日本情報オリンピック 予選4

---

#include<stdio.h>
#include<algorithm>
using namespace std;
int p[110000];
int sum[20][110000];
int sz[20];
int dp[1<<20];
int main(){
    int a,b;scanf("%d%d",&a,&b);
    for(int i=0;i<a;i++){
        scanf("%d",p+i);
        p[i]--;
        sum[p[i]][i+1]++;
        sz[p[i]]++;
    }
    for(int i=0;i<b;i++)for(int j=0;j<a;j++){
        sum[i][j+1]+=sum[i][j];
    }
    for(int i=0;i<(1<<b);i++)dp[i]=999999999;
    dp[0]=0;
    for(int i=0;i<(1<<b);i++){
        int pos=0;
        for(int j=0;j<b;j++)if(i&(1<<j))pos+=sz[j];
        for(int j=0;j<b;j++){
            if(i&(1<<j))continue;
            dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j][pos]);
        }
    }
    printf("%d\n",dp[(1<<b)-1]);
}