Asosiy mazmunga o'tish
STEAM AcademySTEAM Academy

29-dars: Ketma-ketliklar ustida DP

4-darajaPlatina — dinamik programmalash25–32 darslar

Bu darsdan keyin siz

  • ikki ketma-ketlik uchun DP jadvalini quryasiz
  • eng uzun umumiy qism ketma-ketlikni topasiz
  • tahrirlash masofasini hisoblaysiz va uni amalda qayerda ishlashini bilasiz

Avval qo’lda

“Avval qo’lda” bo'limiga havola

Avval qo‘lda

~7 daqiqajuftlikdaKatakli qog'oz

Qog’ozga jadval chizing: yuqori qatorga bdca harflarini, chap ustunga abcb harflarini yozing. Chap yuqori burchakda bo’sh qator uchun nol qatori va nol ustuni bo’lsin.

Har katakni to’ldiring. Qator va ustun harfi bir xil bo’lsa — diagonaldagi songa bir qo’shing. Har xil bo’lsa — tepadagi va chapdagi sonlarning kattarog’ini ko’chiring.

Nimani sezishingiz kerak

O’ng past burchakdagi son — umumiy qism ketma-ketlik uzunligi. Diqqat qiling: siz hech qanday variantni sanamadingiz, faqat jadvalni to’ldirdingiz.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

“Sekin yechim” bo'limiga havola

To’liq izlash birinchi satrning barcha qism ketma-ketliklarini yasab, har birini ikkinchi satrda qidiradi.

sekin.py
def qismmi(kichik, katta):  i = 0  for belgi in katta:      if i < len(kichik) and kichik[i] == belgi:          i += 1  return i == len(kichik)a, b = "abcb", "bdca"eng = 0for maska in range(1 << len(a)):  nomzod = "".join(a[i] for i in range(len(a)) if maska & (1 << i))  if len(nomzod) > eng and qismmi(nomzod, b):      eng = len(nomzod)print(eng)

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
def qismmi(kichik, katta):  i = 0  for belgi in katta:      if i < len(kichik) and kichik[i] == belgi:          i += 1  return i == len(kichik)a, b = "abcb", "bdca"eng = 0for maska in range(1 << len(a)):  nomzod = "".join(a[i] for i in range(len(a)) if maska & (1 << i))  if len(nomzod) > eng and qismmi(nomzod, b):      eng = len(nomzod)print(eng)
Javobni ko'rish
2

«bc» yoki «ba» — ikkita harf. qismmi funksiyasi ikki ko'rsatkich usuli bilan ishlaydi (10-dars): kichik satr bo'ylab bir yurish yetadi.

Nega sekin

“Nega sekin” bo'limiga havola

Birinchi satrning qism ketma-ketliklari soni 2ⁿ. Uzunligi 30 bo’lgan satrda bu milliarddan oshadi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechimn = 15n = 30n = 5 000
Barcha qism ketma-ketliklar2^n32 768sig‘adi10⁹sig‘maydijuda kattasig‘maydi
Jadval (n × m, m = n)n^2225sig‘adi900sig‘adi10⁷sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

“Tez yechim” bo'limiga havola

Holat: dp[i][j] — a ning birinchi i harfi va b ning birinchi j harfi uchun javob. O’tish ikki holatga bo’linadi va uchinchisi yo’q.

tez.py
a, b = "abcbdab", "bdcaba"n, m = len(a), len(b)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):  for j in range(1, m + 1):      if a[i - 1] == b[j - 1]:          dp[i][j] = dp[i - 1][j - 1] + 1      else:          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])print(dp[n][m])

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
a, b = "abcbdab", "bdcaba"n, m = len(a), len(b)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(1, n + 1):  for j in range(1, m + 1):      if a[i - 1] == b[j - 1]:          dp[i][j] = dp[i - 1][j - 1] + 1      else:          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])print(dp[n][m])
Javobni ko'rish
4

«bcba» — to'rtta harf, ikkala satrda ham shu tartibda uchraydi. Jadval 8 x 7 = 56 katakdan iborat, 2⁷ = 128 variant o'rniga.

Tahrirlash masofasi

“Tahrirlash masofasi” bo'limiga havola

Xuddi shu jadval boshqa savolga ham javob beradi: bir satrni ikkinchisiga aylantirish uchun eng kam nechta o’zgartirish kerak? Uchta amal ruxsat etilgan — harf qo’shish, o’chirish va almashtirish.

masofa.py
a, b = "kitob", "kitoblar"n, m = len(a), len(b)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(n + 1):  dp[i][0] = ifor j in range(m + 1):  dp[0][j] = jfor i in range(1, n + 1):  for j in range(1, m + 1):      narx = 0 if a[i - 1] == b[j - 1] else 1      dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + narx)print(dp[n][m])

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
a, b = "kitob", "kitoblar"n, m = len(a), len(b)dp = [[0] * (m + 1) for _ in range(n + 1)]for i in range(n + 1):  dp[i][0] = ifor j in range(m + 1):  dp[0][j] = jfor i in range(1, n + 1):  for j in range(1, m + 1):      narx = 0 if a[i - 1] == b[j - 1] else 1      dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + narx)print(dp[n][m])
Javobni ko'rish
3

«kitob» dan «kitoblar» ga: uchta harf qo'shiladi — l, a, r. Boshlang'ich qiymatlar bu safar nol emas: bo'sh satrdan i harfli satrga o'tish uchun i ta qo'shish kerak.

tahrirlash masofasiedit distance

Bir satrni ikkinchisiga aylantirish uchun kerak bo’ladigan eng kam amal soni. Boshqa nomi — Levenshteyn masofasi.

Bu jadval amalda juda ko’p ishlatiladi: imlo tekshiruvi, qidiruv tizimidagi «balki siz buni nazarda tutgandirsiz», DNK ketma-ketliklarini solishtirish va git diff.

Sinab ko’r

“Sinab ko’r” bo'limiga havola

Vizualda jadval qator-qator to’ladi. Harflar mos kelgan joyda diagonal katakdan bir oshishini kuzating.

LCS — ikki satr jadvali

Harflar mos kelsa diagonaldan bir oshadi, aks holda qo'shnilarning kattarog'i olinadi.

Jadval qator-qator to'ldiriladi; har katakda ikki holatdan biri ishlaydi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

  1. Qatorlar — «abcb» harflari, ustunlar — «bdca» harflari. Birinchi qator va ustun nol: bo'sh satr bilan umumiy qism ham bo'sh.
  2. «a» qatori. Harf mos kelgan joyda diagonal katakka bir qo'shiladi; qolgan joylarda tepadagi va chapdagi kattarog'i olinadi.
  3. «b» qatori. Harf mos kelgan joyda diagonal katakka bir qo'shiladi; qolgan joylarda tepadagi va chapdagi kattarog'i olinadi.
  4. «c» qatori. Harf mos kelgan joyda diagonal katakka bir qo'shiladi; qolgan joylarda tepadagi va chapdagi kattarog'i olinadi.
  5. «b» qatori. Harf mos kelgan joyda diagonal katakka bir qo'shiladi; qolgan joylarda tepadagi va chapdagi kattarog'i olinadi.
  6. Javob — o'ng past burchak: 2. Jami 16 ta katak, ya'ni ikki satr uzunligining ko'paytmasi.
bo'sh
00000
a
0
b
0
c
0
b
0

Qatorlar — «abcb» harflari, ustunlar — «bdca» harflari. Birinchi qator va ustun nol: bo'sh satr bilan umumiy qism ham bo'sh.

Hisoblangan katak0

1/6

Xatoni toping

“Xatoni toping” bo'limiga havola

Tuzoq — xatoni toping

29 / 40

MasalaIkki satrning eng uzun umumiy qism ketma-ketligini toping.

Taklif qilingan yechim

Bu javobning 3-qismi noto'g'ri. Harflar mos kelmaganda diagonaldan olish MUMKIN EMAS: bu ikkala harfni ham tashlab yuborish degani, holbuki faqat bittasini tashlash yetarli. To'g'risi: tepadagi va chapdagi qiymatlarning kattarog'i — max(dp[i-1][j], dp[i][j-1]).

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

O’zingizni sinang

“O’zingizni sinang” bo'limiga havola

1LCS jadvalidagi holat nima?

Javobni ko'rish

dp[i][j] — birinchi satrning i ta va ikkinchi satrning j ta boshlang’ich harfi uchun javob.

2Harflar mos kelmaganda nima qilinadi?

Javobni ko'rish

Tepadagi va chapdagi qiymatlarning kattarog’i olinadi. Ya’ni bitta harfni tashlab, qolganini davom ettiramiz.

3Nol qatori va nol ustuni nimani bildiradi?

Javobni ko'rish

Bo’sh satr holatini. LCS da ular nol, tahrirlash masofasida esa i va j — bo’sh satrdan i harfli satrga o’tish uchun i ta qo’shish kerak.

4Tahrirlash masofasida nechta variant solishtiriladi?

Javobni ko'rish

Uchta: harf qo’shish, o’chirish va almashtirish. Harflar mos kelsa almashtirish bepul bo’ladi.

5Bu jadval amalda qayerda ishlatiladi?

Javobni ko'rish

Imlo tekshiruvi, qidiruv tizimidagi tuzatishlar, DNK tahlili va git diff — hammasi shu jadval ustida quriladi.

Masalalar

“Masalalar” bo'limiga havola

Masalalar

3 ta

  • Edit DistanceCSES 1639o'rta

    Darsdagi ikkinchi jadvalning o‘zi. Boshlang‘ich qiymatlarni to‘g‘ri qo‘ying.

  • Longest Common SubsequenceCSES 3403o'rta

    Uzunlik emas, ketma-ketlikning O‘ZI so‘ralgan. Jadval to‘lgach oxiridan orqaga yuring.

  • Increasing Subsequence IICSES 1748qiyin

    DP va Fenwick daraxti birga ishlaydi (32-dars). Avval n² yechimni yozing.

Lokal mashq: mashqlar/29-lcs/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

“Topshiriq” bo'limiga havola

Topshiriq — darajangizni tanlang

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

abcb va bdca uchun LCS jadvalini qog’ozda to’liq to’ldiring. Keyin javobning o’zini (qaysi harflar) o’ng past burchakdan orqaga yurib toping.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

29-lcs masalasini yeching. Keyin xuddi shu jadvaldan foydalanib tahrirlash masofasini ham hisoblaydigan yechim yozing.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Ismingiz bilan sinfdoshingizning ismi orasidagi tahrirlash masofasini hisoblang. Keyin yechimingizni o’zgartirib, qanday amallar bajarilganini ham chiqaring: qaysi harf qo’shildi, qaysi biri o’chirildi.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.