问题是:
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Link to the question
示例
给定 n = 12,返回 3 因为 12 = 4 + 4 + 4;给定 n = 13,返回 2,因为 13 = 4 + 9。
注意
The approach i have taken is similar to an Integer Knapsack problem with duplicates allowed. First i calculated all the perfect squares which are less than equal to the number n. Now once i have them, the problem is similar to the Integer Knapsack problem. I have a number n and a list of numbers. i want to choose minimum number of numbers from the list such that their sum is equal to n. This problem has a DP solution which i have used.
Out of 586 test cases, i passed 562 test cases and got TLE on the next one. The value of n for that testcase is 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))
'''
提前致谢。
最佳答案
您可以将您的解决方案简化为:
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]
这避免了使用:
- self.min 函数
- 内循环中的除法/取模运算。
- 二维数组
而且速度大约是原来的两倍。
关于algorithm - 求和为 n 的最少完全平方数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45163368/