题解 | #完全平方数的草料#

知识点

动态规划

思路

对于一个数n，它一定能由若干个完全平方数组成，对于j来说，它会由j-i*i转移过来。

设dp[i]代表组成i的最小平方数个数，由于此题需要输出数量尽量少的平方数组合，那么，我们可以先预处理n的平方组成数，然后逆序从大到小地用平方数来组成n，

合法条件为对dp[n-j * j]==dp[n-1],且n>=j * j

代码c++

#include <climits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> numSquares(int n) {
        vector<int>dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
           for(int j=1;j*j<=i;j++)
           {
            dp[i]=min(dp[i],dp[i-j*j]+1);
           }
        }
        vector<int>ans;
        while(n>0)
        {
            for(int i=sqrt(n);i>=1;i--)
            {
                if(dp[n-i*i]+1==dp[n]&&n>=i*i)
                {
                    ans.push_back(i*i);
                    n-=i*i;
                    break;
                }
            }
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};