Хорошо, поэтому я действительно надеюсь, что это не считается «бесстыдной саморекламой», поскольку все эти ссылки относятся к фрагментам кода, которые я разместил на своем личном сайте.Если это неуместно, пожалуйста, дайте мне знать, и я могу их снять.
Вот несколько забавных задач DP, которые в значительной степени классические:в строках A и B найдите наименьшее количество правок (вставок, удалений или замен), необходимых для преобразования A в B. Это называется расстоянием Левенштейна. (Мое решение)
Оптимальное выравнивание последовательности: Для двух строк A и B найдите минимальное количество пробелов, которые должны быть вставлены в последовательность для выравнивания A и B. Это называетсяАлгоритм Нидлмана-Вунша.
(Мое решение) Кратчайшие пути из одного источника: Для ориентированного графа G и одного узла s найдите длины кратчайших путей от s до каждого другого узла в графе,предполагая, что ребра могут быть положительными или отрицательными, но циклов не существует.Это алгоритм Беллмана-Форда.
(Мое решение) Кратчайшие пути всех пар: Для ориентированного графа G найдите минимальные расстояния между всеми парами узлов.Это алгоритм Флойда-Варшалла.
(Мое решение) Надеюсь, это несколько полезно и удачи завтра!