Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

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];
  }
}