Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili 1-masala

8.2 Laboratoriya mashg’uloti
Mavzu: Axborotlar oqimini segmentlarga ajratish. Dinamik darsturlash. Chiziqli model.
Ishning maqsadi: Dinamik dasturlashga doir masalalarga algoritm va dastur tuzish
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
1-masala. Sizga butun kvadrat matritsa (n×n) berilgan. Toshbaqa yuqori chap katakda va pastki o'ng katakga yurish kerak. Bir harakatda toshbaqa qo'shni o'ng yoki qo'shni pastki katakchaga yurishi mumkin. Maksimal yig'indi bilan toshbaqaning yo'lini topish talab qilinadi.
Kirish maʼlumotlari:

2	1	3	5
4	0	1	1
1	1	0	1
0	1	2	7

Variantlarning to'liq ro'yxati universal echimdir. Ro'yxatni amalga oshirish tamoyillari va uning imkoniyatlarini ko'rib chiqing. 4×4 o‘lchamdagi stol bo‘sh. Har qanday yo'l uchta pastga va o'ngga uchta harakatdan iborat. Boshqacha qilib aytganda, 6 ta qadam berilgan, ulardan uchtasi pastga siljish uchun, qolgan uchtasi o'ngga o'tish uchun teriladi.
Oltitadan uchta harakatni tanlash usullari soni ( ) toshbaqa yo'llari sonini aniqlaydi. Umuman olganda, ..
Ushbu misol uchun toshbaqaning 20 ta yo'li bor:

Yo'lning yig'indisini (xarajatini) topishda, jami 100 ta operatsiya uchun beshta qo'shish operatsiyasi talab qilinadi.
Keling, million tezlikka ega kompyuter uchun masalani hal qilish vaqtini hisoblaylik: