当前位置:网站首页>Complete square of leetcode 279

Complete square of leetcode 279

2020-12-06 20:20:02 mind_ programmonkey

Given a positive integer n, Find some perfect squares ( such as 1, 4, 9, 16, …) Make their sum equal to n. You need to minimize the number of complete squares that make up the sum .

Example 1:
Input : n = 12
Output : 3
explain : 12 = 4 + 4 + 4.

Example 2: Input : n = 13
Output : 2
explain : 13 = 4 + 9.

Their thinking :
 Insert picture description here

class Solution {
    
    public int numSquares(int n) {
    
        //  Dynamic programming 
	    	int[] dp = new int[n+1];//  The default initialization values are all 0
	    	for(int i=1;i<=n;i++) {
    
	    		//  The worst case scenario is to do it every time 1 Add up 
	    		dp[i] = i;
	    		//  Update it 
	    		for(int j=1;i-j*j>=0;j++) {
    
	    			dp[i] = Math.min(dp[i],dp[i-j*j]+1);// Dynamic transfer equation 
	    		}
	    	}
	    	return dp[n];
    }
}

版权声明
本文为[mind_ programmonkey]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206201803424h.html