Динамическое программирование

Реализация на С++

int len [n + 1][m + 1];

len[0][0] = 0;

for (int i = 1; i <= n; i++) {

len[i][0] = 0;

}

for (int j = 1; j <= m; j++) {

len[0][j] = 0;

}

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

if (a[i] == b[j]) {

len[i][j] = len[i - 1][j - 1] + 1;

} else {

len[i][j] = max(len[i-1][j], len[i][j-1]);

}

}

}

Восстановление ответу

void restore(int i, int k) {

if ((i == 0) || (k == 0)) {

return;

}

if (a[i] == b[k]) {

restore(i - 1, k - 1);

cout<

} else if (len[i - 1][k] == len[i][k] {

restore(i - 1, k);

} else {

restore(i, k - 1);

}

}

Задача поиска наибольшей увеличивающейся подпоследовательности

Постановка задачи

Отметим, подпоследовательность может и не являться подстрокой (то есть, её элементы не обязательно идут подряд в исходной последовательности). Формально, для строки x длины n необходимо найти максимальное число l и соответствующую ему возрастающую последовательность индексов i₁..i_l, таких что . Наибольшая увеличивающая подпоследовательность имеет применения в физике, математике, теории представления групп, теории случайных матриц. В общем случае известно решение этой задачи за время n log n в худшем случае

int n;

cin>>n;

int a[n+1];

for (int i = 1; i <= n; i++)

cin>>a[i];

int dp[n+1];

for (int i = 1; i <= n; i++) {

dp[i] = 1;

for (int j = 1; j < i; j++) {

if (a[j] < a[i] && dp[j]+1 > dp[i])

dp[i] = dp[j] + 1;

}

}

int ans = 0;

for (int i = 1; i <= n; i++) {

if (dp[i] > ans)

ans = dp[i];

}

1.Гвоздики

(Время: 1 сек. Память: 16 Мб Сложность: 34%)
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.