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]
https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
https://leetcode-cn.com/problems/perfect-squares/solution/shu-ju-jie-gou-he-suan-fa-bfsdong-tai-gu-jl6u/