class Solution { public int numSquares(int n) { /* dp solution , storage - 1d array , meaning - every element will store minimum number of perfect squares it needs to sum to that element algo - solve left to right (smaller to larger) */ int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; for(int i = 2 ; i <= n ; i++){ //subtracting for all perfect squares smaller than i and finding previous answers int min = Integer.MAX_VALUE; for(int j = 1 ; j*j <= i ; j++){ min = Math.min(min,dp[i - j*j]); } //adding 1 for subtracting current perfect square that is // dp[i] = previous answer(dp[i - j*j]) + current(1 which is j*j) // if(min != Integer.MAX_VALUE) dp[i] = min +1; } return dp[n]; } }