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, ;