For example, if n is 10 then output is 2 (9+1)
For example, if n is 13 then output is 2 (9+4)
For example, if n is 12 then output is 3 (4+4+4)
The problem is similar to coin exchange problem. Here we can start to find minimum number for sum of 1 and continue till n
For example n = 4
int dp[] = new int[4]
dp[0] = 0. //
dp[1] = dp[1- (0*0)] + 1 = 1 //the +1 is having the current number in the list
dp[2] = dp[2 - (1*1)] + 1= 1+1 = 2
dp[3] = min of ( dp[3 - (1*1)] or dp[3 - (2*2)]) +1 //2*2 is > 3 so will be ignored
= min(dp[2]) + 1 = 3
dp[4] = min of (dp[4 - (1*1)] or dp[4 - (2*2)] or dp[4-(3*3)]) + 1
= min (dp[3], dp[0]) +1
= min(3,0)+1 = 1
The problem can be solved using dynamic programming where we start from calculating sum for 1 and work towards n.
public class Solution {
int squares(int n) {
int dp[] = new int[n+1];
dp[0] = 0
for (int i = 1;i&lbps;n;i++) {
int j =1;
while (i - (j*j) >= 0) {
dp[i] = Math.min(dp[i], dp[i-(j*j)]);
j++
}
}
return dp[n];
}
}