Барномасозии динамикӣ
Барномасозии динамикӣ — усули ҳал кардани масъалаҳои мураккаб тавассути тақсим кардани онҳо ба зермасъалаҳои содатар.
Ҷадвале дода шудааст аз сатр ва сутун. Дар ҳар як ҳуҷайра , ки , , танга ҷойгир аст.
Дар кунҷи чапи боло сангпушт меистад, яъне дар ҳуҷайраи . Сангпушт метавонад танҳо поён ё ба рост ҳаракат кунад. Ба сангпушт лозим аст то ба ҳуҷайраи расад, ва максималӣ миқдори тангаҳоро ҷамъ кунад.
Ин масъаларо чӣ гуна ҳал кунем? Биёед аввал кӯшиш кунем онро бо ёрии рекурсия ҳал кунем.
Тавассути миқдори максималии тангаҳоро ишора мекунем, ки сангпушт метавонад ҷамъ кунад, агар ӯ аз оғоз кунад ва то ҳуҷайраи расад. Он гоҳ ҷавоб хоҳад буд.
Акнун ба барномасозии динамикӣ бармегардем. Принсипи динамика хеле ба принсипи рекурсия монанд аст.
Ба ёд меорем, ки динамика чист: барномасозии динамикӣ — ин усули ҳал кардани масъала тавассути тақсим кардани он ба зермасъалаҳои содатар аст.
Маҳз ҳаминро мо боло мекардем. Барои ёфтани ҷавоб (ҳангоми ё ) мо қиматҳои масъалаҳои содатарро ҳисоб мекардем — ва .
Дар ин ҳолат:
Одатан ҳангоми ҳал кардани масъалаҳои барномасозии динамикӣ ба мантиқи зерин пайравӣ мекунанд:
Савол ба миён меояд: пас фарқ байни барномасозии динамикӣ ва ҷустуҷӯи рекурсивӣ дар чист?
Дар ҳар ду ҳолат мо ҳолатҳо ва гузаришҳо байни онҳоро дорем.
Фарқ дар он аст, ки дар барномасозии динамикӣ якхела ҳолатҳо чанд маротиба ҳисоб карда намешаванд, дар ҳоле ки дар рекурсияи оддӣ онҳо метавонанд борҳо ҳисоб карда шаванд.
Ба ёд меорем дарси рекурсия бо ёдгирӣ (memoization), ки дар он мо баррасӣ мекардем, чаро рекурсия метавонад якхела қиматҳоро аз нав ҳисоб кунад ва чӣ гуна ин мушкилро ҳал кардан.
Ҳамин ғояро метавон дар ин ҷо ҳам татбиқ кард. Агар ба ҳалли рекурсивӣ ёдгирӣ илова кунем, пас мо дар асл ҳалли бо истифода аз барномасозии динамикиро мегирем.
Сангпушт массиви -ро аз адад ёфт. Ба сангпушт лозим аст баъзе зермаҷмӯи ин ададҳоро интихоб кунад, то ки ҷамъашон дар байни ҳамаи вариантҳои имконпазир максималӣ бошад.
Аммо маҳдудият ҳаст: ду адади ҳамсояро ҳамзамон интихоб кардан мумкин нест.
Ин масъаларо чӣ гуна ҳал кунем?
Ҳолатҳои динамикаро меёбем. Бигзор — ҷамъбасти максималӣ бошад, ки сангпушт метавонад ҷамъ кунад, бо истифода аз танҳо элементҳои префикси дарозии .
Яъне массиви -ро баррасӣ мекунем.
Ҳолатҳои асосӣ:
Акнун баррасӣ мекунем, чӣ гуна -ро ҳангоми ҳисоб кунем. Ду вариант имконпазир аст:
Сангпушт ададро дар мавқеи мегирад.
Он гоҳ ӯ наметавонад -ро гирад, бинобар ин метавонад танҳо префикси
-ро истифода барад.
Ҷамъ дар ин ҳолат баробар аст ба .
Дар натиҷа формулаи динамикаро мегирем:
Ҷавоб ба масъалаи ибтидоӣ қимати хоҳад буд.
Сангпушт ададро дар мавқеи намегирад.
Он гоҳ ӯ метавонад префикси
-ро истифода барад, ва ҷамъ баробар аст ба .
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]);
}