28-dars: Panjarada DP

4-darajaPlatina — dinamik programmalash25–32 darslar

HayotdaShahar

Shahar ko’chalari to’g’ri panjara shaklida. Uydan maktabga faqat sharqqa va janubga yurib borasiz — orqaga qaytmaysiz. Nechta har xil marshrut bor? Ba’zi ko’chalar ta’mirlangan va yopiq.

Bu darsdan keyin siz

• panjarada ikki o’lchovli DP jadvalini to’ldirasiz
• to’siqlarni jadvalda qanday ifodalashni bilasiz
• yo’llarni emas, kataklarni sanash farqini tushuntirasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·yakka·Katakli qog'oz

3 × 4 panjara chizing va bitta katakni qora bo’yang. Chap yuqori burchakdan boshlab, har katakka unga nechta yo’l bilan kelish mumkinligini yozing.

Qoida bitta: katakka faqat yuqoridan va chapdan kelish mumkin, demak uning soni o’sha ikkitasining yig’indisi. Qora katakka hech narsa yozilmaydi.

Nimani sezishingiz kerak

Siz birorta ham yo’lni chizmadingiz — faqat 12 ta katakka son yozdingiz. Javob esa o’ng past burchakda turibdi. Bu — DP.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

To’liq izlash har yo’lni alohida yuradi va oxirida ularni sanaydi.

sekin.pyNusxalash

1panjara = ["....", ".#..", "...."]2r, c = len(panjara), len(panjara[0])3def yur(i, j):4  if i == r - 1 and j == c - 1:5      return 16  soni = 07  if i + 1 < r and panjara[i + 1][j] != "#":8      soni += yur(i + 1, j)9  if j + 1 < c and panjara[i][j + 1] != "#":10      soni += yur(i, j + 1)11  return soni12print(yur(0, 0))

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

Bashorat qilingNusxalash

1panjara = ["....", ".#..", "...."]2r, c = len(panjara), len(panjara[0])3def yur(i, j):4  if i == r - 1 and j == c - 1:5      return 16  soni = 07  if i + 1 < r and panjara[i + 1][j] != "#":8      soni += yur(i + 1, j)9  if j + 1 < c and panjara[i][j + 1] != "#":10      soni += yur(i, j + 1)11  return soni12print(yur(0, 0))

Sizning bashoratingizTekshirish

Javobni ko'rish

4

To'siqsiz 10 ta yo'l bo'lardi. To'siq katagi orqali o'tadigan oltitasi tushib qoladi. Yechim to'g'ri, lekin u har yo'lni oxirigacha yuradi.

Nega sekin

Ish hajmi yo’llar soniga proporsional, panjara o’lchamiga emas. 20 × 20 panjarada yo’llar soni 35 milliardga yaqin.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 100	n = 10 000	n = 10⁶
Har yo‘lni yurish2^n	10³⁰sig‘maydi	juda kattasig‘maydi	juda kattasig‘maydi
Kataklarni to‘ldirishn	100sig‘adi	10 000sig‘adi	10⁶sig‘adi

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

Jadvalda n — panjaradagi kataklar soni. 1000 × 1000 panjara million katakdan iborat va u bemalol to’ldiriladi, yo’llar soni esa astronomik bo’ladi.

Tez yechim

Yo’llarni sanamaymiz — kataklarni to’ldiramiz. Har katakka nechta yo’l bilan kelish mumkinligini bir marta hisoblab, qayta ishlatamiz.

tez.pyNusxalash

1panjara = ["....", ".#..", "...."]2r, c = len(panjara), len(panjara[0])3dp = [[0] * c for _ in range(r)]4for i in range(r):5  for j in range(c):6      if panjara[i][j] == "#":7          continue8      if i == 0 and j == 0:9          dp[i][j] = 110          continue11      yuqoridan = dp[i - 1][j] if i > 0 else 012      chapdan = dp[i][j - 1] if j > 0 else 013      dp[i][j] = yuqoridan + chapdan14for satr in dp:15  print(satr)

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

Bashorat qilingNusxalash

1panjara = ["....", ".#..", "...."]2r, c = len(panjara), len(panjara[0])3dp = [[0] * c for _ in range(r)]4for i in range(r):5  for j in range(c):6      if panjara[i][j] == "#":7          continue8      if i == 0 and j == 0:9          dp[i][j] = 110          continue11      yuqoridan = dp[i - 1][j] if i > 0 else 012      chapdan = dp[i][j - 1] if j > 0 else 013      dp[i][j] = yuqoridan + chapdan14for satr in dp:15  print(satr)

Sizning bashoratingizTekshirish

Javobni ko'rish

[1, 1, 1, 1]
[1, 0, 1, 2]
[1, 1, 2, 4]

To'siq katagi nol bo'lib qoladi va u orqali hech qanday yo'l o'tmaydi. Javob — o'ng past burchak, ya'ni 4.

◆Asosiy g'oya

To’siq uchun alohida shart yozish shart emas: uning dp qiymati nol bo’lib qolgani yetarli. Nol qo’shilganda hech narsa o’zgarmaydi — to’siq o’z-o’zidan yo’lni to’sadi.

Tartib muhim

Jadval chapdan o’ngga, yuqoridan pastga to’ldiriladi va bu tasodif emas. dp[i][j] hisoblanayotganda dp[i-1][j] va dp[i][j-1] allaqachon tayyor bo’lishi kerak.

Bu har DP masalasidagi umumiy qoida: holatlar shunday tartibda hisoblanadiki, har biri faqat allaqachon hisoblanganlarga suyansin. 23-darsdagi «teskari tartibda yig’ish» ham xuddi shu qoidaning boshqa ko’rinishi edi.

Sinab ko’r

Vizualda kataklar birma-bir to’ladi. Har katakning soni faqat ikkita qo’shnidan chiqishini kuzating.

Panjarada DP — yo'llar soni

Katakdagi son — unga nechta yo'l bilan kelish mumkinligi. To'siq orqali yo'l o'tmaydi.

Har katakka kelish usullari soni yuqoridagi va chapdagi kataklar yig'indisiga teng.

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

1. Faqat o'ngga va pastga yurish mumkin. Har katakka nechta yo'l bilan kelish mumkinligini yozib boramiz.
2. Boshlang'ich katak: unga kelishning bitta usuli bor — hech qayerdan kelmaslik.
3. (0, 1): yuqoridan 0, chapdan 1 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
4. (0, 2): yuqoridan 0, chapdan 1 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
5. (0, 3): yuqoridan 0, chapdan 1 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
6. (1, 0): yuqoridan 1, chapdan 0 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
7. (1, 2): yuqoridan 1, chapdan 0 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
8. (1, 3): yuqoridan 1, chapdan 1 — jami 2. Katakka faqat shu ikki tomondan kelish mumkin.
9. (2, 0): yuqoridan 1, chapdan 0 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
10. (2, 1): yuqoridan 0, chapdan 1 — jami 1. Katakka faqat shu ikki tomondan kelish mumkin.
11. (2, 2): yuqoridan 1, chapdan 1 — jami 2. Katakka faqat shu ikki tomondan kelish mumkin.
12. (2, 3): yuqoridan 2, chapdan 2 — jami 4. Katakka faqat shu ikki tomondan kelish mumkin.
13. Javob — o'ng past burchak: 4. Har katak aniq bir marta hisoblandi (11 amal), yo'llar esa alohida yurilmadi.

0

1

x

2

Faqat o'ngga va pastga yurish mumkin. Har katakka nechta yo'l bilan kelish mumkinligini yozib boramiz.

Hisoblangan katak0

OrqagaO‘ynatishOldinga1/13Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

28 / 40

MasalaPanjarada chap yuqoridan o'ng pastga nechta yo'l bor?

Taklif qilingan yechim

1. 1dp[i][j] — (i, j) katagiga nechta yo‘l bilan kelish mumkin.
2. 2dp[0][0] = 1 deb boshlaymiz.
3. 3Jadvalni USTUNMA-USTUN, har ustunni pastdan yuqoriga to‘ldiramiz.
4. 4Javob — o‘ng past burchak.

Bu javobning 3-qismi noto'g'ri. Tartib buzilgan. Pastdan yuqoriga yurilsa, dp[i][j] hisoblanayotganda dp[i-1][j] hali hisoblanmagan bo'ladi va nol sifatida qo'shiladi. Natijada yo'llarning bir qismi yo'qoladi. To'g'ri tartib: har katak o'zidan OLDIN kerak bo'ladigan kataklardan keyin hisoblansin.

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

Javobni ko'rsatish

O’zingizni sinang

1Panjarada DP holati nima?

Javobni ko'rish

dp[i][j] — shu katakka nechta yo’l bilan kelish mumkinligi (yoki masalaga qarab, unga kelishning eng arzon narxi).

2Nega faqat ikkita qo'shni qo'shiladi?

Javobni ko'rish

Faqat o’ngga va pastga yurish mumkin, demak katakka faqat yuqoridan yoki chapdan kelinadi. Boshqa yo’l yo’q.

3To'siq qanday ifodalanadi?

Javobni ko'rish

Uning dp qiymati nol qoldiriladi. Nol qo’shilganda hech narsa o’zgarmaydi, demak to’siq o’z-o’zidan yo’lni to’sadi.

4Jadval to'ldirish tartibining umumiy qoidasi nima?

Javobni ko'rish

Har holat faqat allaqachon hisoblangan holatlarga suyanishi kerak. Panjarada bu chapdan o’ngga, yuqoridan pastga degani.

5Nega javob katta bo'lganda modul olinadi?

Javobni ko'rish

Yo’llar soni juda tez o’sadi: 1000 × 1000 panjarada u yuzlab raqamdan iborat bo’ladi. Shart odatda 10⁹ + 7 ga bo’lgandagi qoldiqni so’raydi.

Masalalar

Masalalar

3 ta

• Grid PathsCSES 1638oson

  Darsdagi masalaning o‘zi, n ≤ 1000. Har qadamda modul olishni unutmang.

• Minimal Grid PathCodeforces 1031Co'rta

  Yo‘llar sanalmaydi — eng arzoni qidiriladi. Faqat bitta amal o‘zgaradi: yig‘ish o‘rniga minimum.

• Edit DistanceCSES 1639o'rta

  Bu ham panjara, faqat kataklar harflar juftligi. 29-darsga tayyorgarlik.

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

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

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

4 × 4 panjara chizing va ikkita katakni to’siq qiling. Jadvalni qo’lda to’ldiring. Keyin to’siqlarni boshqa joyga ko’chiring — javob qanday o’zgardi?

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

28-panjara-yollar masalasini yeching. sekin.py ni 12 × 12 panjarada yurgizib vaqtini o’lchang, keyin tez.py bilan solishtiring.

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

Masalani o’zgartiring: har katakda narx bor va eng arzon yo’l kerak. Qaysi bitta amal o’zgaradi? Keyin yana o’zgartiring: diagonal bo’yicha ham yurish mumkin — endi nima o’zgaradi?

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

Darsni tugatdim