c++ solution, in O(n*sqrt(n)) time and O(n) time.


  • 0
    B

    The solution is simply checking at every perfect square before the number.

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.