Asosiy mazmunga o'tish
STEAM AcademySTEAM Academy

26-dars: DP 1D

4-darajaPlatina — dinamik programmalash25–32 darslar

Bu darsdan keyin siz

  • har DP masalasida uchta savolga javob berasiz: holat, o’tish, boshlang’ich qiymat
  • rekursiyani jadvalga o’girasiz va nega bu kerakligini bilasiz
  • O(n²) DP ni O(n log n) ga tushirish g’oyasini ko’rasiz

Avval qo’lda

“Avval qo’lda” bo'limiga havola

Avval qo‘lda

~6 daqiqajuftlikda8 ta kartochka

Sakkizta kartochkaga sonlar yozing, masalan 7 3 5 3 6 2 9 8, va ularni qatorga tering. Tartibini o’zgartirmang.

Har kartochka ostiga bitta son yozing: shu kartochka bilan tugaydigan eng uzun o’suvchi zanjir uzunligi. Chapdan o’ngga yuring — oldingi javoblardan foydalanishingiz mumkin.

Nimani sezishingiz kerak

Har son uchun siz chapdagi kichikroq sonlarni qaradingiz va ularning javoblaridan eng kattasiga bir qo’shdingiz. Bu — DP o’tishi. Javob esa pastki qatordagi eng katta son.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Uchta savol

“Uchta savol” bo'limiga havola

Har dinamik programmalash masalasi uchta savolga javob berish bilan boshlanadi. Ular tartibda so’raladi va tartib muhim.

holatstate

dp[i] aynan nimani anglatishi. Bir gapda, aniq. Noaniq holat butun yechimni buzadi.

o'tishtransition

Bitta holat qiymati boshqa holatlardan qanday chiqishi.

Uchinchisi — boshlang’ich qiymat: hech narsaga bog’liq bo’lmagan, to’g’ridan-to’g’ri ma’lum holatlar.

Sekin yechim

“Sekin yechim” bo'limiga havola

Masalamiz uchun uchta javob shunday. Holat: dp[i] — aynan i-son bilan tugaydigan eng uzun o’suvchi ketma-ketlik. O’tish: dp[i] chapdagi kichikroq sonlarning eng yaxshisiga bir qo’shish. Boshlang’ich qiymat: har son yolg’iz o’zi zanjir, ya’ni 1.

sekin.py
a = [7, 3, 5, 3, 6, 2, 9, 8]dp = [1] * len(a)for i in range(len(a)):  for j in range(i):      if a[j] < a[i] and dp[j] + 1 > dp[i]:          dp[i] = dp[j] + 1print(dp)print(max(dp))

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

Bashorat qiling
a = [7, 3, 5, 3, 6, 2, 9, 8]dp = [1] * len(a)for i in range(len(a)):  for j in range(i):      if a[j] < a[i] and dp[j] + 1 > dp[i]:          dp[i] = dp[j] + 1print(dp)print(max(dp))
Javobni ko'rish
[1, 1, 2, 1, 3, 1, 4, 4]
4

Javob dp ning oxirgi elementi emas, ENG KATTASI: eng uzun zanjir ro'yxatning oxirida tugashi shart emas. Bu eng ko'p qilinadigan xato.

Diqqat qiling: bu yerda rekursiya yo’q. Jadval chapdan o’ngga to’ldiriladi va dp[i] hisoblanayotganda undan chapdagilar allaqachon tayyor bo’ladi. Rekursiya chuqurligi muammosi yo’qoldi.

Nega sekin

“Nega sekin” bo'limiga havola

Ikkita ichma-ich sikl: n². Chegara esa n ≤ 200000.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechimn = 1 000n = 5 000n = 200 000
Har juftni ko‘rishn^210⁶sig‘adi10⁷sig‘adi10¹⁰sig‘maydi
Ikkilik qidiruv bilann log n9 966sig‘adi61 439sig‘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

Butunlay boshqa fikr. Uzunliklarni emas, har uzunlik uchun eng qulay oxirni saqlaymiz: oxir[k] — uzunligi k+1 bo’lgan zanjirlarning eng kichik oxirgi elementi.

Bu ro’yxat har doim o’suvchi bo’ladi, demak unda ikkilik qidiruv ishlaydi (7-dars).

tez.py
from bisect import bisect_lefta = [7, 3, 5, 3, 6, 2, 9, 8]oxir = []for x in a:  i = bisect_left(oxir, x)  if i == len(oxir):      oxir.append(x)  else:      oxir[i] = xprint(oxir)print(len(oxir))

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

Bashorat qiling
from bisect import bisect_lefta = [7, 3, 5, 3, 6, 2, 9, 8]oxir = []for x in a:  i = bisect_left(oxir, x)  if i == len(oxir):      oxir.append(x)  else:      oxir[i] = xprint(oxir)print(len(oxir))
Javobni ko'rish
[2, 5, 6, 8]
4

Uzunlik to'g'ri, lekin oxir ro'yxatining O'ZI javob emas: [2, 5, 6, 8] haqiqiy zanjir emas. U faqat har uzunlik uchun eng qulay oxirni saqlaydi.

Sinab ko’r

“Sinab ko’r” bo'limiga havola

Vizualda dp jadvali chapdan o’ngga to’ladi. Har son uchun qaysi oldingi son tanlanganiga e’tibor bering.

1D DP — eng uzun o'suvchi ketma-ketlik

Har son uchun undan oldingi eng foydali son qidiriladi.

dp[i] har son uchun alohida hisoblanadi: undan oldingi kichikroq sonlar ichidan eng uzun zanjir tanlanadi.

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

  1. dp[i] — aynan i-son bilan TUGAYDIGAN eng uzun o'suvchi ketma-ketlik uzunligi. Har son o'zi bilan boshlanishi mumkin, demak boshlang'ich qiymat 1.
  2. 7 dan oldin undan kichik son yo'q (yoki ular foyda bermaydi). dp = 1.
  3. 3 dan oldin undan kichik son yo'q (yoki ular foyda bermaydi). dp = 1.
  4. 5 ni 3 ustiga ulash eng foydali: dp = 1 + 1 = 2.
  5. 3 dan oldin undan kichik son yo'q (yoki ular foyda bermaydi). dp = 1.
  6. 6 ni 5 ustiga ulash eng foydali: dp = 2 + 1 = 3.
  7. 2 dan oldin undan kichik son yo'q (yoki ular foyda bermaydi). dp = 1.
  8. 9 ni 6 ustiga ulash eng foydali: dp = 3 + 1 = 4.
  9. 8 ni 6 ustiga ulash eng foydali: dp = 3 + 1 = 4.
  10. Javob — dp dagi eng katta son: 4. Jami 28 ta taqqoslash ketdi, ya'ni n kvadrat. Ikkilik qidiruv bilan buni n log n ga tushirish mumkin.
sonlar
7031523364259687
dp

dp[i] — aynan i-son bilan TUGAYDIGAN eng uzun o'suvchi ketma-ketlik uzunligi. Har son o'zi bilan boshlanishi mumkin, demak boshlang'ich qiymat 1.

Taqqoslash0

1/10

Xatoni toping

“Xatoni toping” bo'limiga havola

Tuzoq — xatoni toping

26 / 40

MasalaEng uzun o'suvchi qism ketma-ketlik uzunligini toping.

Taklif qilingan yechim

Bu javobning 4-qismi noto'g'ri. Javob oxirgi elementning dp qiymati emas, dp dagi ENG KATTA qiymat. Eng uzun zanjir ro'yxatning oxirida tugashi shart emas. Masalan [1, 2, 3, 0] da dp = [1, 2, 3, 1] va javob 3, dp[n-1] esa 1.

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

O’zingizni sinang

“O’zingizni sinang” bo'limiga havola

1DP masalasida qaysi uchta savolga javob beriladi?

Javobni ko'rish

Holat (dp[i] nimani anglatadi), o’tish (u boshqa holatlardan qanday chiqadi) va boshlang’ich qiymat (nima to’g’ridan-to’g’ri ma’lum).

2Jadval ko'rinishining rekursiyadan afzalligi nima?

Javobni ko'rish

Rekursiya chuqurligi muammosi yo’qoladi. Jadval chapdan o’ngga to’ldirilganda kerakli qiymatlar allaqachon tayyor bo’ladi.

3Nega javob dp[n-1] emas?

Javobni ko'rish

Eng uzun zanjir ro’yxatning oxirida tugashi shart emas. Javob — max(dp).

4oxir ro'yxati nimani saqlaydi?

Javobni ko'rish

Har uzunlik uchun shu uzunlikdagi zanjirlarning eng kichik oxirgi elementini. Uning uzunligi javob beradi, lekin uning o’zi haqiqiy zanjir emas.

5Nega oxirni kichik saqlash foydali?

Javobni ko'rish

Oxir qanchalik kichik bo’lsa, keyingi sonni unga ulash imkoniyati shuncha katta. Ya’ni kichik oxir kelajakni ko’proq ochiq qoldiradi.

Masalalar

“Masalalar” bo'limiga havola

Masalalar

3 ta

  • Increasing SubsequenceCSES 1145o'rta

    Darsdagi masalaning o‘zi, n ≤ 2·10⁵. n² yechim o‘tmaydi.

  • Removing DigitsCSES 1637oson

    Holat: dp[x] — x ni nolga tushirish uchun eng kam qadam. O‘tish — har raqamni ayirib ko‘rish.

  • Longest Regular Bracket SequenceCodeforces 5Cqiyin

    Stek (11-dars) va DP birga ishlaydi. Holat: shu belgida tugaydigan eng uzun to‘g‘ri qavs.

Lokal mashq: mashqlar/26-lis/ — 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

4 1 7 3 8 2 9 ketma-ketligi uchun dp jadvalini qog’ozda to’ldiring. Javob nechta chiqdi va u qaysi kartochkada tugadi?

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

26-lis masalasini yeching. sekin.py ni n = 200000 bilan yurgizishga urinib ko’ring va necha soniya ketganini yozing.

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

Tez yechimni o’zgartirib, zanjirning o’zini ham chiqaring — faqat uzunligini emas. Ishora: har element uchun uni qaysi elementga ulaganingizni saqlab boring.

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