DSAlgo.cc
Войти
Динамическое программирование
Расстояние Левенштейна
НОП (LCS)
Рюкзак 0/1
Размен монет
Рекуррентное соотношение
d
p
i
,
j
=
{
max
(
i
,
j
)
если
i
=
0
или
j
=
0
d
p
i
−
1
,
j
−
1
если
a
i
=
b
j
1
+
min
(
d
p
i
−
1
,
j
,
d
p
i
,
j
−
1
,
d
p
i
−
1
,
j
−
1
)
иначе
dp_{i,j} = \begin{cases} \htmlClass{dp-case-active}{\max(i, j) } &\htmlClass{dp-case-active}{ \; \text{если } i = 0 \text{ или } j = 0} \\[2pt] dp_{i-1,\,j-1} & \; \text{если } a_i = b_j \\[2pt] 1 + \min(dp_{i-1,\,j},\; dp_{i,\,j-1},\; dp_{i-1,\,j-1}) & \; \text{иначе} \end{cases}
d
p
i
,
j
=
⎩
⎨
⎧
max
(
i
,
j
)
d
p
i
−
1
,
j
−
1
1
+
min
(
d
p
i
−
1
,
j
,
d
p
i
,
j
−
1
,
d
p
i
−
1
,
j
−
1
)
если
i
=
0
или
j
=
0
если
a
i
=
b
j
иначе
Выравнивание строк
С
У
Б
Б
О
Т
А
С
О
Б
О
Л
Ь
Таблица ДП
текущая
зависимости
путь
СУББОТА \\ СОБОЛЬ
∅
С
О
Б
О
Л
Ь
∅
0
С
У
Б
Б
О
Т
А
Шаг 1 / 56 — считаем
dp[0][0]
· Базовый случай: пустые префиксы
Строка A
Строка B
Скорость (ячеек/с)