Create 14_pefectSquares.cpp

FazeelUsmani · web-flow · commit 44123703df25 · 2021-10-14T11:09:46.000+05:30
diff --git a/10 October LeetCode Challenge 2021/14_pefectSquares.cpp b/10 October LeetCode Challenge 2021/14_pefectSquares.cpp
@@ -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];
+    }
+};
