思路：

還是比較好想的，g[i]定義為和為 i 的完全平方數(shù)的最少數(shù)量。那么遞推關(guān)系式是g[i]=min(g[i-1],g[i-4],g[i-9],...)+1，數(shù)組初始化是g[0]=0,g[1]=1。注意這里要對(duì)g[0]初始化，（舉個(gè)例子）因?yàn)樵诒闅v到g[4]時(shí)，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]