perfect_squares 

 1from functools import cache
 2from math import floor, sqrt
 3
 4
 5# @leet start
 6class Solution:
 7    def numSquares(self, n: int) -> int:
 8        """
 9        This question asks us to return the minimum number of squares to
10        sum up to a number. This can be done with lagrange's theorem, but I
11        did the DP version instead, where I test all numbers in $O(n^2)$ time that
12        add up to the number and return the shortest path.
13        """
14
15        @cache
16        def dp(n):
17            if n <= 1:
18                return n
19            if n == floor(sqrt(n)) ** 2:
20                return 1
21
22            min_count = n
23            for i in range(1, floor(sqrt(n)) + 1):
24                min_count = min(min_count, dp(n - i * i))
25            return min_count + 1
26
27        return dp(n)
28
29
30# @leet end
31
32
33def test():
34    assert 2 + 2 == 4
class Solution: 
 7class Solution:
 8    def numSquares(self, n: int) -> int:
 9        """
10        This question asks us to return the minimum number of squares to
11        sum up to a number. This can be done with lagrange's theorem, but I
12        did the DP version instead, where I test all numbers in $O(n^2)$ time that
13        add up to the number and return the shortest path.
14        """
15
16        @cache
17        def dp(n):
18            if n <= 1:
19                return n
20            if n == floor(sqrt(n)) ** 2:
21                return 1
22
23            min_count = n
24            for i in range(1, floor(sqrt(n)) + 1):
25                min_count = min(min_count, dp(n - i * i))
26            return min_count + 1
27
28        return dp(n)
def numSquares(self, n: int) -> int: 
 8    def numSquares(self, n: int) -> int:
 9        """
10        This question asks us to return the minimum number of squares to
11        sum up to a number. This can be done with lagrange's theorem, but I
12        did the DP version instead, where I test all numbers in $O(n^2)$ time that
13        add up to the number and return the shortest path.
14        """
15
16        @cache
17        def dp(n):
18            if n <= 1:
19                return n
20            if n == floor(sqrt(n)) ** 2:
21                return 1
22
23            min_count = n
24            for i in range(1, floor(sqrt(n)) + 1):
25                min_count = min(min_count, dp(n - i * i))
26            return min_count + 1
27
28        return dp(n)

This question asks us to return the minimum number of squares to sum up to a number. This can be done with lagrange's theorem, but I did the DP version instead, where I test all numbers in $O(n^2)$ time that add up to the number and return the shortest path.

def test(): 
34def test():
35    assert 2 + 2 == 4