总计n的完美平方数的最少数量

Question

问题是:

给定正整数n,找到总和为n的最小正方数(例如,1,4,9,16 ......).链接到问题

例

给定n = 12,返回3,因为12 = 4 + 4 + 4; 给定n = 13,返回2,因为13 = 4 + 9.

注意

我采用的方法类似于允许重复的整数背包问题.首先,我计算了所有小于n的完美正方形.现在,一旦我拥有它们,问题类似于整数背包问题.我有一个数字n和一个数字列表.我想从列表中选择最小数量,使其总和等于n.这个问题有一个我用过的DP解决方案.

在586个测试用例中,我通过了562个测试用例并在下一个测试用例中获得了TLE.该测试用例的n值为3428.

我提交的解决方案:

class Solution(object):
    def numSquares(self,n):
        if(n == 0):
            return 0
        if(n == 1):
            return 1
        squares = self.findSquares(n) # returns a list of perfect squares <= n
        rows = len(squares)
        cols = n + 1
        mat = []
        for i in range(rows):
            mat.append([0] * cols)

        for i in range(cols):
            mat[0][i] = i

        for i in range(rows):
            mat[i][0] = 0

        min = mat[0][cols - 1]
        for i in range(1,rows):
            for j in range(1,cols):
                if(j < squares[i]):
                    mat[i][j] = mat[i - 1][j]

                else:
                    mat[i][j] = self.min(mat[i - 1][j], (j // squares[i] + (mat[i][j % squares[i]])))
                if(j == cols - 1 and mat[i][j] < min):
                    min = mat[i][j]
        '''
        for i in range(rows):
            for j in range(cols):
                print(mat[i][j],end=" ")
            print()
            '''
        return min

    def min(self,a,b):
        if(a <= b):
            return a
        else:
            return b


    def findSquares(self,n):

        i = 1
        squares = []
        while (i * i <= n):
            squares.append(i * i)
            i = i + 1
        return squares
'''
x = Solution()

print(x.numSquares(43))
'''

提前致谢.

Answer 1

您可以将解决方案简化为：

def numSquares(self,n):
    if(n == 0):
        return 0
    if(n == 1):
        return 1
    squares = self.findSquares(n)
    rows = len(squares)
    cols = n + 1
    mat = [n] * cols
    mat[0] = 0

    for s in squares:
        for j in range(s,cols):
            mat[j] = min(mat[j], 1 + mat[j - s])

    return mat[n]

这可以避免使用：

1. self.min 函数
2. 内循环中的除法/取模运算。
3. 二维数组

并且速度大约是两倍。