Динамическое программирование и логические формулы

Динамическое программирование - фаворит многих интервьюеров во время собеседований по программированию - оно проверяет вашу стратегию формулирования проблемы, хорошее использование рекурсивных алгоритмов и структур данных (в основном, многомерные массивы или хэш-таблицы), а также проверяет вашу способность рассуждать о сложности вычислений. рекурсивного алгоритма с мемоизацией.

Давайте разберемся с проблемой динамического программирования в неожиданном месте. Проблема была задана QuantCast. Не стесняйтесь просматривать другие сообщения о большинстве случаев динамического программирования.

Проблема

Вам представлен массив, представляющий логическое выражение. Элементы бывают двух видов:

Определите количество способов сгруппировать элементы массива, используя круглые скобки, чтобы все выражение оценивалось как True.

Например, предположим, что введено ['F', '|', 'T', '&', 'T']. В этом случае есть две приемлемые группы: (F | T) & T и F | (T & T).

Решение

Как и во многих других проблемах, этот пример дает потенциальный намек на решение. В данном примере мы разделяем входной массив в разных местах (в данном случае в логических операторах | и &) и объединяем полученные решения. Это намекает на рекурсивное решение разделяй и властвуй:

Перебрать весь массив символов.
Всякий раз, когда мы сталкиваемся с логическим оператором (|, &, ^), разбиваем массив на две части и рекурсивно находим скобки для этих двух частей.
Объедините два решения с помощью логического оператора, чтобы составить полное решение.

Предположим, что наш исходный массив называется symbols, и предположим, что symbols[i] является логическим оператором. Мы собираемся разделить массив на два подмассива - symbols[0...i-1] (называется left) и symbols[i+1...n] (называется right). Определим четыре числа:

false_left = количество скобок для left, которые оцениваются как ложные.
true_left = количество скобок для left, которые оцениваются как истинные.
false_right = количество скобок right, которые оцениваются как ложные.
true_right = количество скобок для right, которые оцениваются как истинные.

Очень важно правильно объединить эти четыре числа с помощью оператора symbols[i], чтобы весь массив был истинным. Мы можем использовать следующую таблицу, чтобы объединить их:

У нас будет аналогичная таблица для расчета количества способов объединения результатов подмассивов, чтобы получить оценку всего массива как ложь.

Учитывая эту рекурсивную формулировку, очень легко закодировать рекурсивное решение проблемы. Большинству кандидатов должно быть комфортно его кодировать. Однако разработка рекурсивной формулировки - это только часть битвы! Ваше решение будет выделяться, если вы воспользуетесь тем фактом, что многие рекурсивные вызовы алгоритма совместно используют решение. Для любого значения i символы [0..i-1] могут передаваться в качестве аргументов рекурсивному методу несколько раз. Это наблюдение является отличительной чертой динамического программирования.

Когда решение проблемы может быть построено из решений подзадач, говорят, что проблема демонстрирует оптимальную подструктуру. Если, кроме того, если несколько подзадач имеют общее решение, проблему можно решить с помощью динамического программирования.

Динамическое программирование обеспечивает эффективное решение путем кэширования результатов подзадачи в хэш-таблице (часто называемой таблицей мемоизации) при первом вызове подзадачи. Каждый последующий вызов подзадачи просто использует более быстрый поиск в кеше (вместо повторного выполнения вычислений) для возврата решения.

Вот как будет работать мемоизация для нашего примера - наш исходный массив symbols = ['F', '|', 'T', '&', 'T']. Допустим, мы пытаемся решить подмассив symbols[2...4] = ['T', '&', 'T'].

Число способов заключить в скобки подмассив для вычисления true - один: (T & T)
Нет способов заключить подмассив в круглые скобки, чтобы оценить его как false.

После вычисления этой информации мы сохраняем ее в двух таблицах:

true_table[['T', '&', 'T']] = 1
false_table[['T', '&', 'T']] = 0

Любой последующий вызов того же подмассива ищет в true_table и false_table и возвращает результаты (1 или 0) вместо повторного вычисления скобок.

Приведенная выше формулировка динамического программирования вдохновляет следующую рекурсивную функцию C ++:

Сложность

Сложность алгоритма, очевидно, определяется сложностью рекурсивного метода find_parenthesization. Взгляните на этот метод - сколько раз он вызывается? Метод принимает два индекса в массиве, start и end. Оба они могут принимать любое значение от 1 до n, где n - размер массива. Более того, из-за мемоизации каждая пара (начало, конец) передается рекурсивной функции не более одного раза! Поскольку существует O (n²) пар индексов, рекурсивный метод вызывается не более O (n²) раз. При каждом вызове мы потенциально перебираем весь подмассив symbols[start...end], выполняя O (n) объем работы. Следовательно, общая временная сложность алгоритма составляет O (n²) * O (n) = O (n³). Поскольку мы поддерживаем карту, содержащую не более O (n²) пар формы (start, end), общая пространственная сложность алгоритма составляет O (n²).

Единичные тесты

Давайте напишем несколько хороших модульных тестов и сделаем наше интервью действительно выдающимся! Мы рассмотрим несколько простых случаев (пустой массив, пусто истинный и ложный массив и т. Д.). Мы также напишем тесты для нескольких сложных случаев, в том числе и в постановке задачи.

Первоначально опубликовано на https://cppcodingzen.com 19 января 2021 г.

Динамическое программирование и логические формулы