Ежедневный вопрос по алгоритму — leetcode 279 — полное квадратное число — python

алгоритм
Ежедневный вопрос по алгоритму — leetcode 279 — полное квадратное число — python

【Название Описание】

[Метод 1: динамическое программирование]

Заполнение дп снизу вверх, по идее проблем нет, но время подачи истекло.

 def numSquares(self, n: int) -> int:
        dp=[i for i in range(n+1)]
        for i in range(4,n+1):
            for j in range(int(n**0.5),1,-1):
                if i>=j**2:
                    dp[i]=min(dp[i],dp[i-j*j]+1)
        return dp[n]

【Метод 2: BFS】

Это эквивалентно началу с корневого узла 0 и расширению вниз слой за слоем.Элементы, которые можно добавить к каждому слою, представляют собой квадрат 1 в квадрате int (n ** 0,5), который одинаков для каждого узла. .

from collections import deque
class Solution:
    def numSquares(self, n):
        selected=[i**2 for i in range(1,int(n**0.5)+1)]
        visited = set()
        queue=deque([(0,0)])
        while(queue):
            current,height=queue.popleft()
            for i in selected:
                sum_= current+i
                if sum_==n:
                    return height+1
                if sum_<n and sum_ not in visited:
                    visited.add(sum_)
                    queue.append((sum_,height+1))
Категории