surbhi498
diff --git a/‎10 October LeetCode Challenge 2021/14_pefectSquares.cpp
Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions b/‎10 October LeetCode Challenge 2021/14_pefectSquares.cpp
Copy file name to clipboard
+18Lines changed: 18 additions & 0 deletions
@@ -0,0 +1,18 @@
+class Solution {
+public:
+    int numSquares(int n) {
+        //vector for updating the dp array/values
+        vector<int> dp(n+1,INT_MAX);
+        //base case
+        dp[0]=0;
+        int count = 1;
+        while(count*count <= n) {
+        int sq = count*count;
+        for(int i = sq; i < n+1; i++) {
+            dp[i] = min(dp[i-sq] + 1,dp[i]);
+        }
+        count++;
+    }
+    return dp[n];
+    }
+};