福田做棋牌网站建设哪家公司便宜宁波百度快照优化排名

思路：

还是比较好想的，g[i]定义为和为 i 的完全平方数的最少数量。那么递推关系式是g[i]=min(g[i-1],g[i-4],g[i-9],...)+1，数组初始化是g[0]=0,g[1]=1。注意这里要对g[0]初始化，（举个例子）因为在遍历到g[4]时，g[4]=min(g[4-1],g[4-4])+1。

代码：

C++：

class Solution {
public:int numSquares(int n) {vector<int> g(n+1,0x3f3f3f3f);g[0]=0,g[1]=1;for(int i=2;i<=n;i++){for(int j=1;i-j*j>=0;j++){int temp=j*j;g[i]=min(g[i],g[i-temp]+1);}}return g[n];}
};

Python：

class Solution:def numSquares(self, n: int) -> int:g=[0x3f3f3f3f]*(n+1)g[0]=0g[1]=1for i in range(2,n+1):j=1while i-j*j>=0:temp=j*jg[i]=min(g[i],g[i-temp]+1)j+=1return g[n]