logo头像
Snippet 博客主题

【Leetcode 279】Perfect Squares

难度: 中等(Medium)

题目:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

思路:首先构造出小于n的平方序列,然后将n拆分为两部分,一个是某个平方数的整数倍,另一个是余数,在所有拆分的可能中选择需要次数最小的即可。计算余数所需最少次数与问题具有相同结构,因而可递归求解,并且在求解过程中会涉及计算重复问题,所以需保留中间解的答案。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def getLeast(self, squares, dp, n):
if n == 0:
return 0
elif n in squares:
return 1
elif n in dp:
return dp[n]
else:
t = min([n/k+self.getLeast(squares,dp,n%k) for k in squares if k<=n])
dp[n] = t
return t

def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n==None or n<=0:
return -1
squares = []
for i in range(1,n+1):
if i*i > n:
break
squares.append(i*i)
dp = {}
return self.getLeast(squares,dp,n)

评论系统未开启,无法评论!