aboutsummaryrefslogtreecommitdiff
path: root/perfect_squares.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'perfect_squares.cpp')
-rw-r--r--perfect_squares.cpp23
1 files changed, 23 insertions, 0 deletions
diff --git a/perfect_squares.cpp b/perfect_squares.cpp
new file mode 100644
index 0000000..677c4a0
--- /dev/null
+++ b/perfect_squares.cpp
@@ -0,0 +1,23 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int numSquares(int n) {
+ vector<int> dp(n + 1, INT_MAX);
+ dp[0] = 0;
+ for (int target = 1; target <= n; target++) {
+ int mmCount = INT_MAX;
+ for (int num = 1; num <= sqrt(target); num++) {
+ int sqNum = pow(num, 2), curr = 1 + dp[target - sqNum];
+ mmCount = min(mmCount, curr);
+ }
+ dp[target] = mmCount;
+ }
+ return dp[n];
+ }
+};
+
+int main() {
+ Solution obj;
+ cout << obj.numSquares(12);
+}