Share my C++ DP solution


  • 0
    V
    class Solution {
    public:
        int numSquares(int n) {
            if (n < 1) return 0;
            vector<int> least_dp(n+1, INT_MAX);
            int i = 0, j = 0, perfectNum = 0, end = 0;
            least_dp[0] = 0;
            
            for (i = 1; i <= n; ++i)
            {
                end = (int)sqrt(i);
                for (j = 1; j <= end; ++j)
                {
                    perfectNum = j * j;
                    if (least_dp[i] > (1 + least_dp[i - perfectNum]))
                        least_dp[i] = 1 + least_dp[i - perfectNum];
                }
            }
            
            return least_dp[n];
        }
    };

Log in to reply
 

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