Учитывая целое число 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]

Удачного кодирования !!