Submask bo‘yicha DP

Submask (bitmask) bo‘yicha DP

Submask DP — bu bitmask texnikasi bo‘lib, fiksirlangan maska uchun biz samarali tarzda uning barcha submaskalarini ko‘rib chiqamiz.

Asosiy usul: maskaning barcha submaskalarini ko‘rib chiqish

m maskasi uchun bu sikl m ning barcha noldan farqli submaskalari bo‘ylab o‘tadi:

Agar sizga 0 submaskasi ham kerak bo‘lsa, uni alohida qayta ishlang.

Nega bu ishlaydi?

• s - 1 eng kichik o‘rnatilgan bitni va undan keyingi barcha bitlarni o‘zgartiradi
• & m asl maskada yo‘q bitlarni olib tashlaydi
• shuning uchun biz m submaskalari ichida qolamiz

Murakkablik haqidagi fakt (juda muhim)

Agar siz submaskalar bo‘yicha siklni har bir maska uchun ishga tushirsangiz, umumiy murakkablik:

$O(3^n)$

Sabab: har bir bit uchun 3 ta variant bor:

• maskada yo‘q
• maskada bor, lekin submaskada yo‘q
• ham maskada, ham submaskada bor

Misol: to‘plamni ruxsat etilgan guruhlarga bo‘lish

Faraz qilaylik:

• ok[s] s kichik to‘plami ruxsat etilgan guruh ekanini aytadi
• Biz m maskani qoplash uchun minimal guruhlar sonini xohlaymiz

Bo‘lsin:

$dp[m] = m \text{ ni qoplash uchun guruhlar minimumi}$