Dinamik dasturlash
Dinamik dasturlash — murakkab masalalarni ularni sodda kichik masalalarga bo‘lish orqali yechish usuli.
ta satr va ta ustundan iborat jadval berilgan. Har bir katakda, bu yerda , , ta tanga bor.
Chap yuqori burchakda toshbaqa turibdi, ya’ni katakda. Toshbaqa faqat pastga yoki o‘ngga harakatlana oladi. Toshbaqa maksimal miqdordagi tangalarni yig‘ib, katakka yetib borishi kerak.
Bu masalani qanday yechish mumkin? Keling, avval uni rekursiya yordamida yechib ko‘ramiz.
orqali toshbaqa dan boshlasa va katakka yetib borsa, yig‘ishi mumkin bo‘lgan maksimal tangalar sonini belgilaymiz. Unda javob bo‘ladi.
Endi dinamik dasturlashga qaytamiz. Dinamika prinsipi rekursiya prinsipiga juda o‘xshaydi.
Dinamika nima ekanini eslaymiz: dinamik dasturlash — masalani uni sodda kichik masalalarga bo‘lish orqali yechish usuli.
Aynan shuni biz yuqorida qildik. javobini topish uchun ( yoki bo‘lganda) biz sodda masalalarning qiymatlarini — va ni hisobladik.
Bu holatda:
Odatda dinamik dasturlash masalalarini yechishda quyidagi mantiqqa amal qilinadi:
Savol tug‘iladi: unda dinamik dasturlash bilan rekursiv ko‘rib chiqish o‘rtasidagi farq nimada?
Har ikkala holatda ham bizda holatlar va ular orasidagi o‘tishlar bor.
Farq shundaki, dinamik dasturlashda bir xil holatlar bir necha marta hisoblanmaydi, oddiy rekursiyada esa ular ko‘p marta hisoblanishi mumkin.
Qiymatlarni eslab qolish (memoization) bilan rekursiya darsini eslaymiz, u yerda rekursiya nega bir xil qiymatlarni qayta-qayta hisoblab chiqishi va bu muammoni qanday hal qilish mumkinligini ko‘rib chiqqan edik.
Xuddi shu g‘oyani bu yerda ham qo‘llash mumkin. Agar rekursiv yechimga eslab qolishni qo‘shsak, biz amalda dinamik dasturlashdan foydalangan holda yechim olamiz.
Toshbaqa ta sondan iborat massivini topdi. Toshbaqaga bu sonlarning qandaydir qism to‘plamini tanlash kerak, shunda ularning yig‘indisi barcha mumkin bo‘lgan variantlar orasida maksimal bo‘lsin.
Biroq cheklov bor: bir vaqtning o‘zida ikkita qo‘shni sonni tanlash mumkin emas.
Bu masalani qanday yechish mumkin?
Dinamika holatlarini topamiz. — toshbaqa faqat uzunligi bo‘lgan prefiks elementlaridan foydalanib yig‘ishi mumkin bo‘lgan maksimal yig‘indi bo‘lsin.
Ya’ni massivini ko‘rib chiqamiz.
Bazaviy holatlar:
Endi bo‘lganda ni qanday hisoblashni ko‘rib chiqamiz. Ikki variant bo‘lishi mumkin:
Toshbaqa pozitsiyadagi sonni oladi.
Unda u ni ola olmaydi, shuning uchun faqat
prefiksidan foydalanishi mumkin.
Bu holatda yig‘indi ga teng.
Natijada dinamika formulasi hosil bo‘ladi:
Boshlang‘ich masalaning javobi qiymati bo‘ladi.
Toshbaqa pozitsiyadagi sonni olmaydi.
Unda u
prefiksidan foydalanishi mumkin, yig‘indi esa ga teng.
int Rec(int x, int y) {
if (x == 1 && y == 1) {
return C[1][1];
} else {
int best = 0;
if (x > 1) {
best = max(best, Rec(x - 1, y));
}
if (y > 1) {
best = max(best, Rec(x, y - 1));
}
return best + C[x][y];
}
}
map<pair<int, int>, int> mem;
int Rec(int x, int y) {
if (x == 1 && y == 1) {
return C[1][1];
} else {
if (mem.find({x, y}) != mem.end()) {
return mem[{x, y}];
}
int best = 0;
if (x > 1) {
best = max(best, Rec(x - 1, y));
}
if (y > 1) {
best = max(best, Rec(x, y - 1));
}
return mem[{x, y}] = best + C[x][y];
}
}
dp[0] = 0;
dp[1] = a[1];
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 2] + a[i], dp[i - 1]);
}