Clean cpp Dp solution


  • 0
    Z
    	class Solution {
    public:
    	int numSquares(int n) {
    	   
    		vector<int> nums;
    		vector<int> dp(n+1,INT_MAX);
    		for(int i=1;i*i<=n;i++){
    			nums.push_back(i*i);
    			dp[i*i] = 1;
    		}
    		
    		for(int i=1;i<n;i++)
    			for(int j=0;j<nums.size();j++){
    				if(dp[i]!=INT_MAX&&i+nums[j]<=n)
    					dp[i+nums[j]] = min(dp[i+nums[j]] , dp[i]+1);
    			}
    		return dp[n]==INT_MAX?n:dp[n];	
    	}
    };

Log in to reply
 

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