6-Laboratoriya ishi Mavzu: Dinamik programmalash

1-masala: SMS lar soni
Masala sharti:
Knopkali telefonlarda klaviaturasi quyidagicha bo’ladi.

Masalan C harfini terish uchun 2-tugmani 3 marta bosish kerak. Ko’pi bilan k marta knopka bosish orqali nechta har xil SMS yozish mumkinligi sonini aniqlash talab qilinadi.
Yechimi:

1. 
   Dinamika holati: dp [m] - m marta bosish orqali hosil qilingan har xil SMS lar soni.
   
2. 
   Boshlang’ich holatlar: Nol marta bosish orqali uzunligi nolga teng bo’lgan bitta SMS hosil qilish mumkin ya’ni dp [0] = 1;
   
3. 
   Qayta hisoblash formulasi: Yozish uchun bir, ikki, uch marta bosish zarur bo’lgan 8 ta harf va yana 4 marta bosish talab qiladigan ikkita harf bor.
   

dp[m] = (dp[m-1]+dp [m-2]+dp [m-3]) * 8 + dp [m-4] * 2.

4. 
   Hisoblash tartibi: Uch usuldan istalganidan foydalanish mumkin.
   
5. 
   Javob: Barcha holatlar yig’indisi, ;
   

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.