Разделите плитку шоколада на кусочки, минимизируя площадь недопустимых кусочков.

Учитывая двумерный массив, arr[][] и кусок плитки шоколада размера N × M , задача состоит в том, чтобы найти минимально возможную сумму площадей недопустимых частей, разделив плитку шоколада на одну или несколько частей, где кусок шоколада считается недействительным, если размер этого кусочка не соответствует ни одной заданной паре.

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

Примеры:

Input: N = 10, M =10, arr[][] = {{1, 2}}
Output: 0
Explanation:
Divide the given chocolate bar of dimension (10, 10) into 50 pieces of dimension (1, 2) or (2, 1), not leaving any left over pieces, hence output is zero.

Input: N = 10, M =10, arr[][] = {{3, 5}}
Output: 10

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

• Разделите плитку шоколада всеми возможными способами, т.е. сделайте все возможные вертикальные и горизонтальные разрезы один за другим и для каждого случая рекурсивно найдите решение для получившихся кусочков.
• Для базового случая просто проверьте, действительно ли текущее деление:
  • Если он действителен, верните ноль.
  • В противном случае попробуйте разделить его на допустимые части, используя описанный выше подход, если его нельзя разделить дальше на допустимые части, верните площадь части.

Временная сложность: O(N + M) ^{(N + M)}
Вспомогательное пространство: O(1)

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы использовать динамическое программирование, поскольку описанный выше подход имеет перекрывающиеся подзадачи, которые необходимо вычислять более одного раза, а для сокращения этих вычислений используйте табулирование или запоминание. Общее количество различных кусочков шоколада, которые можно изготовить, равно только N × M , поэтому приведенный выше алгоритм имеет N × M состояний.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив dp[][] для хранения minInvalidAreaUtil(l, b) в dp[l][b], ok[][] для хранения шоколадных конфет допустимого размера (i, j) в ok[i][j] = 1 и ок[j][i] = 1.
• Для каждого состояния, является ли текущая часть (l, b) действительной или нет, в постоянное время из таблицы поиска ok[][]
  • Если текущая часть (l, b) действительна, то есть ok[l][b] == 1 . Следовательно, верните dp[l][b] = 0
  • В противном случае вычислите его, сделав все возможные вертикальные и горизонтальные разрезы один за другим, и для каждого случая найдите решение для полученных частей. Следовательно, обновите dp[l][b].
• Выведите окончательный ответ как minInvalidAreaUtil(l, b).

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * M * (N + M))
Вспомогательное пространство: O(N * M)