Динамикалык программалоо: негиздер
Динамикалык программалоо: абалдар, өтүүлөр, база — тепкич жана максималдуу кесинди.
Динамикалык программалоо (ДП) — кайталанып кесилишкен подмаселелерге бөлүнгөн маселелерди чечүү методу: ар бир подмаселени БИР жолу чечип, жоопту эстеп калабыз.
Үч суроодон турган рецепт:
1. Абал: dp[i] деген эмне? (сөз менен, так!)
2. Өтүүлөр: dp[i] кичине абалдар аркылуу кантип туюнтулат?
3. База: эң кичине абалдар эмнеге барабар?
ДПнын hello-world мисалы — тепкич: n тепкичтүү тепкичтин түбүндө турасыз жана 1 же 2 тепкичке кадам таштайсыз. Канча жол менен чыгууга болот?
• dp[i] — i тепкичине жетүүнүн жолдорунун саны;
• i тепкичине i-1 же i-2 тепкичинен келишет, демек dp[i] = dp[i-1] + dp[i-2];
• база: dp[0] = 1 (түбүндө турабыз), dp[1] = 1.
Тепкич. n киргизиңиз, 80ге чейин, мисалы: 10
n = 10 үчүн жооп 89 — булар маселенин ичинен өзүнөн өзү өсүп чыккан Фибоначчи сандары.
ДП жазуунун эки стили:
• таблицалык (жогорудагыдай): массивди базадан өйдө карай толтурабыз;
• мемоизация: рекурсия жазып, жоопторду кештейбиз. Кайсынысы ыңгайлуу — табит иши, татаалдыгы бирдей.
Экинчи классика — кесиндинин максималдуу суммасы (Кадане алгоритми). Абал: dp[i] — i позициясында АЯКТАГАН кесиндинин максималдуу суммасы. Өтүү: же мурунку кесиндини улантабыз, же a[i] менен жаңысын баштайбыз.
Максималдуу кесинди. Киргизиңиз: 8, андан кийин -2 1 -3 4 -1 2 1 -5
Мисалдагы жооп: 6 (4 -1 2 1 кесиндиси). Байкаңыз: dp-массиви бул жерде бир cur өзгөрмөсүнө кыскарды — өтүү мурунку абалды гана караганда көп учурда ушундай болот.
Тапшырма: кээ бир тепкичтерге басууга тыюу салынган «тепкичти» чечиңиз (тыюу салынгандар үчүн dp[i] = 0). Жана кадамдар 1, 2 жана 3 болгондо маселе кандай өзгөрөрүн ойлонуңуз.
Сабакты өттүм деп белгилеңиз — 4-деңгээл аяктады. Алдыда тереңдетилген ДП!