1. 题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和
的完全平方数的个数最少。

2. 题解

动态规划

3. 代码

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