ДП по подмножествам, ДП по профилю

Вопросы, на которые вы должны сами отвечать

1. Что считаем?
2. Как считаем?
3. В каком порядке считаем?
4. Какие начальные значения?
5. Где ответ?

Гамильтонов путь

dp[last][mask] = min длина Гамильтонова пути из S в Last, если посетить вершины mask
dp[last][mask] -> dp[next][mask | (1 << next)]
next не принадлежит mask
last->next есть в графе
𝒪(2^n * n^2)

Начальные значения:
dp[s][1 << s] = 0, остальные - INF

Где ответ?
dp[i][полная маска]

Кол-во гамильтоновых путей из вершины S

dp[last][mask] = кол-во Гамильтоновых путей из S в last, если посетили вершины mask
dp[last][mask] -> dp[next][mask | (1 << next)]
next не принадлежит mask
last->next есть в графе
dp[s][1 << s] = 1
dp[next][mask | (1 << next)] += dp[last][mask]

Ответ?
SUM dp[i][(1 << n) - 1]

Введите текст

Есть числа 0...2^n - 1
a[0], a[1], .. a[2^n - 1]
Для каждой mask посчитать сумму:
SUM a[i], где i - подмаска нашей маски

Пример:
mask = 6 = 100
a[000] + a[010] + a[100] + a[110]

int n;
for(int mask = 0; mask < (1 << n); mask++){
    for(int submask = mask; submask > 0; submask=(submask - 1)&mask){
        ...
    }
}

dp[mask][i] - сумма a[submask], где биты 0...I в mask и subtask могут различаться, а остальные совпадают

dp[mask][0] = a[mask]
Если i-тый бит mask = 0, то dp[mask][i + 1] = dp[mask][i]
Иначе dp[mask][i + 1] = dp[mask][i] + dp[mask ^ (1 << i)][i]

for(int i = 0; i < n; i++){
    for(int mask = 0; mask < (1 << n); mask++){
        dp[mask][i + 1] = dp[mask][i]
        if((mask >> i) & 1){
            dp[mask][i + 1] += dp[mask ^ (1 << i)][i]
        }
    }
}

Оптимизация: можно сделать dp - одномерным, тогда получим такой код:

for(int i = 0; i < n; i++){
    for(int mask = 0; mask < (1 << n); mask++){
        if((mask >> i) & 1){
            dp[mask] += dp[mask ^ (1 << i)]
        }
    }
}

Работает столько же, но памяти намного меньше

пошли нафиг

https://wiki.algocode.ru/index.php?title=ДП_по_профилю