Учитывая целое число n
, верните наименьшее количество полных квадратов, сумма которых равна n
.
Полный квадрат - это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на себя. Например, 1
, 4
, 9
и 16
являются точными квадратами, а 3
и 11
- нет.
Подход:
Подход грубой силы предлагает использовать рекурсивную функцию для поиска всех комбинаций полных квадратов, сумма которых должна быть нацелена. Затем найдите длину комбинации, имеющей минимальную длину. Но это будет работать только с небольшими числами. Для больших чисел будет выброшено TLE.
Мы решаем эту проблему, используя подход «сверху вниз». Мы начинаем с данного числа и продолжаем вычитать полные квадраты меньше числа. Делаем так, пока не дойдем до нуля. Давайте возьмем пример 12. Итак, полные квадраты меньше 12 - это 1, 4 и 9. Таким образом, в любой момент мы можем уменьшить число на 1, 4 или 9. Этот процесс сгенерирует приведенное ниже дерево решений.
На каждом уровне мы пытаемся увидеть, достигли ли мы числа, равного нулю или точного квадрата.
В сгенерированном дереве мы замечаем, что у нас много повторяющихся подзадач.
Если мы удалим подзадачи, мы получим следующее дерево.
Если мы вырвемся из процесса в тот момент, когда мы получим нулевой или полный квадрат на любом уровне, это еще больше сократит вычисления.
Реализация кода:
import math, collections def numSquares(n): pf_sq = set([x**2 for x in range(1, math.ceil(n ** 0.5) + 1)]) if n in pf_sq: return 1 seen = {n} queue = collections.deque([(n, 0)]) while queue: target, count = queue.popleft() if target == 0: return count if target in pf_sq: return count + 1 for square in pf_sq: new_target = target - square if new_target == 0: return count + 1 if new_target in pf_sq: return count + 2 if new_target not in seen and new_target > 0: queue.append((new_target, count + 1)) seen.add(new_target) print(numSquares(11))
В приведенном выше решении мы использовали очередь для реализации обхода BFS.
значения очереди в итерации для приведенного выше примера:
(12,0) (11,1), (8,1), (3,1) (8,1), (3,1), (10,2), (7,2), (2,2), (4,2)
visible (set) предназначен для того, чтобы избежать повторных вычислений.
Подход 2:
В этом подходе мы наращиваем от [0], [1, 4,9], [2, 5, 10, 5, 8, 10], пока не достигнем цели.
Подход 2: DP
В этом случае мы строим цель из более мелких целей.
def numSquares(n): dp = [n]*(n+1) dp[0] = 0 dp[1] = 1 for target in range(2, n+1): tmp = int(math.sqrt(target)) for s in range(tmp, 0, -1): sq = s*s dp[target] = min(dp[target], dp[target - sq] + 1) if dp[target] == 2 or dp[target] == 1: break return dp[n]
Удачного кодирования !!