题目描述
https://leetcode-cn.com/problems/perfect-squares/
思路题解
完全背包
一开始的思路：n=6665的时候，时间超限
class Solution:
def numSquares(self, n: int) -> int:
if n<4:return n
dp=[10001]*(n+1)
dp[1],dp[2],dp[3],dp[4]=1,2,3,1
for i in range(5,n+1):
if math.sqrt(i)%1!=0:
for j in range(1,i//2+1):
dp[i]=min(dp[i-j]+dp[i-(i-j)],dp[i])
else:dp[i]=1
return dp[n]
看了下答案， 进行了改进
class Solution:
def numSquares(self, n: int) -> int:
if n<4:return n
dp=[i for i in range(n+1)]
for i in range(2,n+1):
j=1
while j*j<=i:
dp[i]=min(dp[i-j*j],dp[i])
j+=1
dp[i]+=1
return dp[n]