leetcode-279. Perfect Squares 完全平方数

Given a positive integer n, find the least number of perfect square numbers (for example,  1, 4, 9, 16, ... ) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3  解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: 2 解释: 13 = 4 + 9. 在真实的面试中遇到过这道题？

思路：建一个n+1长度的dp数组，将第一个值初始化为0，其余值都初始化为INT_MAX，i从0循环到n，j从1循环到i+j*j<=n的位置，然后每次更新dp[i+j*j]的值，动态更新dp数组，dp[i]表示正整数i至少能由多少个完全平方数组成，那也就是求n，最终返回dp[n]即可。 

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1 ,INT_MAX);
        dp[0]= 0;
        for(int i=0;i<=n;++i)
        {
            for(int j=1;i+j*j<=n;++j)
                dp[i+j*j]=min(dp[i+j*j],dp[i]+1);
        }
        return dp.back();
    }
};