6-Laboratoriya ishi Mavzu: Dinamik programmalash

2-masala. Ot

Masala sharti:

NxM shaxmat doskasining (1,1) katagida ot turibdi. Uning quyidagi rasmda ko’rsatilgandek 4 xil tipli yurish orqali (N, M) katakga necha xil usulda boorish mumkinligini aniqlang.



Yechimi:

1. 
   Dinamika holatlari: dp[i][j] – bu (i, j) katakga borishning har xil usullari son
   
2. 
   Boshlabg’ich qiymatlar: (1, 1) katakga bir xil usul bilan kelish mumkin.
   
3. 
   Qayta hisblash formulasi:
   

To’g’ri tartib uchun

dp[i][j] = dp[i - 2][j - 1] + dp[i - 2][j + 1] + dp[i - 1][j - 2] + dp[i + 1][j - 2]

Teskari tartib uchun

dp[i + 1][j + 2] += dp[i][j]

dp[i + 2][j + 1] += dp[i][j]

dp[i - 1][j + 2] += dp[i][j]

dp[i + 2][j - 1] += dp[i][j]

4. 
   Bu yerda tartib eng muhm ahamiyatga ega. Uni satr bo’yicha yoki ustun bo’yicha o’tib bo’lmaydi. Chunki hozir turgan yacheykadagi natija undan oldingi va keyingi ustunlarga shuningdek undan oldingi va keyingi satrlarga bog’liq.
   

Bu masalani yechishning ikki hil variant bor:

1. 
   Qaydaydir yaxshi ko’rib chiqish tartibini aniqlash
   
2. 
   Erinchoq dinamikadan foydalanish
   

Agar erinchoq dinamikadan foydalansak bu eng yaxshi usul hisoblanadi. Uning o’zin hisoblahni hal qiladi.

Agar qandaydir tartibda ko’rib chiqmoqchi bo’lsak uni masalanan quyidagi tartibda ko’rib chiqish kerak, diagonal tartibda:

Bunday tartibda o’tib chiqish to’g’ri tartibda ham teskari tartibda ham to’g’ri bo’ladi.

5. 
   Javob bu dp[n][m] ning qiymati.