Q14 Perfect Squares - LeetCode
Thu Mar 02 2023 14:03:44 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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];
}
}
content_copyCOPY
https://leetcode.com/problems/perfect-squares/
Comments