#algorithm
Вопрос:
Это проблема программирования.
Предположим, что у нас есть массив n x m, и каждая сетка содержит целое число, большее или равное 0.
введите описание изображения здесь
Мы можем нарисовать вертикальную или горизонтальную линию. В сетке, где проходит эта строка, число в ней будет уменьшено на единицу (не менее 0).
Пример: Если мы проведем горизонтальную линию.
введите описание изображения здесь
Итак, сколько строк нам нужно, по крайней мере, чтобы свести числа в сетке к нулю?
Я думал об использовании метода поиска методом грубой силы и метода динамического программирования, но нет четких доказательств того, что моя идея верна.
Может ли кто-нибудь помочь мне решить эту проблему? Спасибо.
Ответ №1:
Я думаю, что подход динамического программирования довольно ясен и доказуем.
Вы начинаете с одноэлементного списка вашей стартовой сетки.
На каждом этапе вы берете каждую сетку в текущем списке и для каждой строки и столбца в этой сетке, которые еще не полностью равны нулю, создаете новую сетку, в которой все ячейки в этой строке или столбце уменьшены на единицу. Затем удалите дубликаты. Считайте этапы, пока не получите сетку с нулем.
Это можно оптимизировать, создав только две новые сетки для каждой сетки, выбрав строку или столбец для самой высокой оставшейся ячейки.