(LeetCode 动态规划（基础版）) 279. 完全平方数 (动态规划dp)

思路：动态规划dp，类似于完全0、1背包的问题，时间复杂度0(n*sqrt(n))。

C++版本：

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

JAVA版本：

class Solution {public int numSquares(int n) {int[] v=new int[n+10];Arrays.fill(v,n);v[0]=0;for(int i=1;i<=n/i;i++){for(int j=i*i;j<=n;j++){v[j]=Math.min(v[j],v[j-i*i]+1);}}return v[n];}
}

Go版本：

func numSquares(n int) int {v:=make([]int,n+10)for i:=1;i<=n;i++ {v[i]=n;}v[0]=0for i:=1;i<=n/i;i++ {for j:=i*i;j<=n;j++ {v[j]=min(v[j],v[j-i*i]+1);}}return v[n]
}