Бузургтарин зерпайдарпаии умумӣ (БЗУ)
Бузургтарин зерпайдарпайии умумӣ (БЗУ)
Шарти масъала
Дода шудаанд ду пайдарпайӣ ва . Талаб мешавад дарозии калонтарин зерпайдарпайии умумиро ёфтан.
Бузургтарин зерпайдарпайии умумӣ (БЗУ)
Дода шудаанд ду пайдарпайӣ ва . Талаб мешавад дарозии калонтарин зерпайдарпайии умумиро ёфтан.
Масалан, калонтарин зерпайдарпайии умумии ва ин мебошад.
-ро ҳамчун ҳал барои префикси бо дарозии ва префикси бо дарозии ишора мекунем. Яъне, дарозии калонтарин зерпайдарпайии умумии ва .
Ҳолатҳои базавӣ инҳоянд:
Акнун кӯшиш мекунем гузаришҳоро барои ҳолати умумӣ пайдо кунем. Биёед гузаришҳоро баррасӣ кунем:
Пас, формуларо дорем:
Биёед барои ҳар як ҳолати ғайрибазавӣ гузариши беҳтаринро дар хотир нигоҳ дорем. Яъне, мо медонем, ки се гузариши гуногун дорад:
Масиви дигар -ро месозем ва дар нигоҳ медорем, ки кадом гузариш барои беҳтарин аст. Масалан, агар бошад, он гоҳ дорем.
Пас аз ин мо метавонем ҷавобро барқарор кунем. -ро инициализатсия мекунем ва то он даме, ки ва бошад, корҳои зеринро мекунем.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = 0;
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
if (a[i] == b[j]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = -1;
if (dp[i - 1][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][j];
p[i][j] = 1;
}
if (dp[i][j - 1] > dp[i][j]) {
dp[i][j] = dp[i][j - 1];
p[i][j] = 2;
}
if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
p[i][j] = 3;
}
}
}
vector<int> res;
int x = n, y = m;
while (x > 0 && y > 0) {
if (p[x][y] == 3) {
res.push_back(a[x]);
x -= 1;
y -= 1;
} else if (p[x][y] == 2) {
y -= 1;
} else { // p[x][y] == 1
x -= 1;
}
}
reverse(res.begin(), res.end());