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 - 1eng kichik o‘rnatilgan bitni va undan keyingi barcha bitlarni o‘zgartiradi& masl maskada yo‘q bitlarni olib tashlaydi- shuning uchun biz
msubmaskalari ichida qolamiz
Murakkablik haqidagi fakt (juda muhim)
Agar siz submaskalar bo‘yicha siklni har bir maska uchun ishga tushirsangiz, umumiy murakkablik:
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]skichik to‘plami ruxsat etilgan guruh ekanini aytadi- Biz
mmaskani qoplash uchun minimal guruhlar sonini xohlaymiz
Bo‘lsin: