Динамическое программирование - очень популярный алгоритмический подход в соревновательном программировании. Динамическое программирование, сокращенно DP, является одной из самых важных тем как в контексте соревнований по программированию, так и в интервью по программированию многих крупных технологических гигантов, таких как Amazon, Google, Microsoft, Facebook и так далее. о том, как определить проблему DP на примерах некоторых очень популярных проблем DP.
Что такое DP?
На мой взгляд, DP - это улучшенная форма рекурсии. Рекурсия вместе с оптимизацией приводит к решению DP. Концепция заключается в запоминании и использовании ответов на более мелкие «подзадачи», которые уже решены. Это значительно снижает временную сложность проблем по сравнению с рекурсией. Другое важное наблюдение заключается в том, что всякий раз, когда рекурсия имеет 2 или более вызовов, высока вероятность использования DP.
Как определить проблему DP?
Я лично считаю, что DP - это улучшенная форма рекурсии. Хотя иногда DP действительно сбивает с толку, я на собственном опыте убедился, что рекурсивное размышление о решениях и проблемах значительно упрощает достижение решения DP. Итак, если у кого-то есть хорошее понимание и знания о рекурсии, он / она может легко решить проблемы DP. Теперь, возвращаясь к моему вопросу об идентификации проблемы DP, обычно есть 2 способа идентифицировать проблему DP:
- Проблема, основанная на выборе
- Оптимальные задачи
Проблемы, основанные на выборе, - это проблемы, при которых есть выбор или возможность выбрать конкретный объект или нет. Это проблемы, основанные на ситуации, когда есть выбор рассмотреть или отклонить конкретную сущность. Например, 0–1 Задача о ранце. Проблема простая. Дан массив веса и значений размера n, состоящий из n объектов. Здесь w [i] - вес i-го объекта, а val [i] обозначает значение i-го объекта. Вам также дается вместимость сумки W. Ваша задача - максимизировать прибыль, складывая предметы в сумку.
Для каждого объекта вы должны проверить, меньше ли вес объекта максимальной емкости W. Если вес объекта больше W, то его нельзя поместить в сумку, в противном случае у вас есть 2 варианта: размещать ли это объект в сумке или отклонить этот объект и рассмотреть другие объекты
if (w1 ›W) - Отклонить
if (w1 ‹W) - отклонить или принять (есть выбор)
Я не углубляюсь в проблему рюкзака и не собираюсь дальше решать эту проблему, что я могу сделать позже в какой-то момент, но моя единственная цель здесь заключалась в том, чтобы подвергнуть вас таким ситуациям, когда вы должны сделать выбор. Я надеюсь, что это так. вам ясно.
Оптимальные проблемы - это те проблемы, для которых необходимо найти оптимальное решение - наибольшее / наименьшее / максимальное / минимальное и т. д.
Давайте возьмем пример самой длинной общей подпоследовательности из двух строк. Это очень классическая задача DP, в которой вам нужно найти самую длинную общую подпоследовательность.
Сделайте следующий ввод
6 6
ABCDGH
AEDFHR
LCS двух вышеперечисленных строк - это «ADH», а его длина равна 3.
Простой рекурсивный код для указанной выше проблемы:
int LCS (строка x, строка y, int n, int m)
{
if (n == 0 || m == 0) return 0;
if (x [n- 1] == Y [m-1])
return 1 + LCS (x, y, n-1, m-1);
else
return max (LCS (x, y , n-1, m), LCS (x, y, n, m-1));
}
Рекурсия является родителем DP. Рекурсивный код может быть преобразован в решение DP путем мемоизации. Мемоизация в основном используется для решения проблемы повторного вычисления одних и тех же проблем снова и снова, что также известно как перекрывающиеся проблемы, и сохраняет решение для конкретного входа. Если тот же вход будет снова вызван позже, нам не придется решать его снова, и мы можем легко извлечь эти данные из уже сохраненных результатов. Для осуществления запоминания мы составляем таблицу или матрицу и сохраняем в ней результаты.
Код DP для LCS:
int main () {
Введите m, n, x, y
int t [n + 1] [m + 1]; // Создание матрицы
memset (t, -1, sizeof (t)); // Инициализация
LCS (x, y, n, m);
}
int LCS (строка x, строка y, int n, int m)
{
if (n == 0 || m == 0) return 0;
if (t [n] [m]! = - 1)
return t [m] [n];
if (x [n-1] == Y [m-1])
t [n] [m] = 1 + LCS (x, y, n-1, m-1);
иначе
t [n] [m] = max (LCS (x, y, n-1, m), LCS (x, y, n, m-1));
}
Надеюсь, эта статья даст вам некоторое представление о DP и о том, как его можно идентифицировать. Я бы хотел, чтобы в будущем я мог публиковать статьи о том, как преобразовать рекурсивное решение в решение DP.
Будьте на связи!!
