DP-и зермаска

DP-и зерниқоб

Submask DP як техникаи битмаск аст, ки дар он, барои як маскаи собит, мо тавассути ҳамаи зермаскаҳои он ба таври самаранок мегузарем.

Ҳиллаи асосӣ: Гузаштан аз ҳамаи зермаскаҳои як маска

Барои маскаи m, ин давр аз ҳамаи зермаскаҳои ғайрисифрии m мегузарад:

Агар ба шумо зермаскаи 0 ҳам лозим бошад, онро ҷудогона коркард кунед.

Чаро кор мекунад?

• s - 1 пасттарин бити гузошташударо ва ҳамаи битҳои баъди онро тағйир медиҳад
• & m битҳои берун аз маскаи аслиро хориҷ мекунад
• бинобар ин мо дар дохили зермаскаҳои m мемонем

Далели мураккабӣ (хеле муҳим)

Агар шумо даври зермаскаро барои ҳар як маска иҷро кунед, мураккабии умумӣ чунин аст:

$O(3^n)$

Сабаб: барои ҳар як бит, 3 интихоб вуҷуд дорад:

• дар маска нест
• дар маска ҳаст, аммо дар зермаска нест
• ҳам дар маска ва ҳам дар зермаска ҳаст

Мисол: Тақсим кардани маҷмӯа ба гурӯҳҳои дуруст

Фарз мекунем:

• ok[s] нишон медиҳад, ки оё зермаҷмӯаи s як гурӯҳи дуруст аст
• Мо мехоҳем шумораи ҳадди ақали гурӯҳҳоро барои пӯшонидани маскаи m

Бигзор:

$dp[m] = \text{шумораи ҳадди ақали гурӯҳҳо барои пӯшонидани } m$